【題意】:地圖中有K種物品, 沒(méi)有收集資源時(shí),每走一步用能量1,挖掘和收集資源 i 需要能量Ai ,收集了資源 i 后, 每走一步,消耗能量需要加Bi。問(wèn)最后收集完K種物品并且回到起點(diǎn)的最小消耗。

【題解】:采用了優(yōu)先隊(duì)列+狀態(tài)壓縮bfs,這里要預(yù)處理好攜帶了狀態(tài)s的代價(jià)cost[s],之后的bfs該怎么做就怎么做。這里用優(yōu)先隊(duì)列有個(gè)好處,這樣就保證每次出隊(duì)的都是最優(yōu)的點(diǎn),相比用一個(gè)數(shù)組來(lái)記錄,更省空間,并且代碼量也少了。

【代碼】:
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "queue"
 5 using namespace std;
 6 char maz[25][25];
 7 int k, p, r, c;
 8 int a[15], b[15], cost[1<<11];
 9 const int dx[] = {010-1};
10 const int dy[] = {-1010};
11 int sx, sy;
12 bool visit[25][25][1<<11];
13 
14 struct pos {
15     int x, y, cost, collect;
16     pos() {}//構(gòu)造函數(shù)
17     pos(int a, int b, int c, int d) {
18         x = a, y = b, cost = c, collect = d;
19     }
20     bool operator< (const pos &a) const {
21         return cost > a.cost;
22     }
23 };
24 
25 bool check(int x, int y) {
26     return x >= 0 && x < r && y >= 0 && y < c;
27 }
28 
29 int bfs() {
30     priority_queue<pos> que;
31     memset(visit, falsesizeof(visit));
32     que.push(pos(sx, sy, 00));
33     visit[sx][sy][0= true;
34     while(!que.empty()) {
35         pos now = que.top();
36         que.pop();
37         int x = now.x, y = now.y, collect = now.collect, ncost = now.cost + cost[collect] + 1;
38         if(ncost > p) continue;
39         for(int i = 0; i < 4; i++) {
40             int nx = x + dx[i], ny = y + dy[i];
41             if(!check(nx, ny) || maz[nx][ny] == '#' || visit[nx][ny][collect]) continue;
42             if(nx == sx && ny == sy) {
43                 if(collect == (1 << k) - 1return ncost;
44                 continue;
45             }
46             if(maz[nx][ny] <= 'Z' && maz[nx][ny] >= 'A') {
47                 int t = maz[nx][ny] - 'A';
48                 if((collect & (1 << t)) == 0) {
49                     que.push(pos(nx, ny, ncost + a[t], collect | (1<<t)));
50                     visit[nx][ny][collect|(1<<t)] = true;
51                 }
52             }
53             que.push(pos(nx, ny, ncost, collect));
54             visit[nx][ny][collect] = true;
55         }
56     }
57     return -1;
58 }
59 
60 int main() {
61     int T;
62     scanf("%d"&T);
63     while(T--) {
64         scanf("%d%d%d%d\n"&r, &c, &k, &p);
65         for(int i = 0; i < r; i++) {
66             for(int j = 0; j <= c; j++) {
67                 scanf("%c"&maz[i][j]);
68                 if(maz[i][j] == '*') sx = i, sy = j;
69             }
70         }
71         for(int i = 0; i < k; i++) scanf("%d%d"&a[i], &b[i]);
72         memset(cost, 0sizeof(cost));
73         for(int t = 0; t < (1 << k); t++)
74             for(int j = 0; j < k; j++)
75                 if(t & (1 << j)) cost[t] += b[j];
76         int ans = bfs();
77         if(ans == -1) printf("Impossible\n");
78         else printf("%d\n", ans);
79     }
80     return 0;
81 }