题意：
一个n*m的迷宫，在t时刻后就会坍塌，问：在逃出来的前提下，能带出来多少价值的宝藏。
其中：
’*‘：代表墙壁；
'.'：代表道路；
'@'：代表起始位置；
'<'：代表出口；
'A'~'J'：代表宝藏；
解题思路：
本题有两种思路：1，bfs+状态压缩；相比之下耗时多；
2，bfs+dfs；耗时较少；
在这里着重介绍第一种方法：（博主也是现学现卖啦^_^）
因为宝藏的数目比较少，所以我们可以对宝藏进行状态压缩（用二进制表示宝藏是否已经拾取，1表示已拾取，0表示未拾取），
标记数组vis[i][x][y],i就是宝藏的拾取状态，（x，y）是当前搜索位置；（当然知道这些也不一定能ac）。
注意：（想要把题目ac的看过来）
1：不可能输出“Impossible”。
2：题目中的数据问题，题目的例子相当于有一个围墙，而可能数据并不总是如此。
3：首先是如何判断当前的路径是否应该结束（并不是到‘<’为止，因为可能还有时间到达其他的宝藏)。
下面就祝大家ac愉快啦
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 #define N 55 8 9 struct node 10 { 11 int x, y, z, t, val; 12 }; 13 14 int n, m, t, num; 15 int vis[1<<11][N][N], va[15], dir[4][2] = {1,0, -1,0, 0,1, 0,-1}; 16 char map[N][N]; 17 18 int bfs (int sx, int sy) 19 { 20 int num = -1; 21 22 queue<node>Q; 23 node cur, next; 24 25 cur.x = sx, cur.y = sy; 26 cur.val = cur.t = cur.z = 0; 27 memset (vis, 0, sizeof(vis)); 28 vis[0][sx][sy] = 1; 29 30 Q.push(cur); 31 while (!Q.empty()) 32 { 33 cur = Q.front(); 34 Q.pop(); 35 36 if (map[cur.x][cur.y] == '<') 37 { 38 if (cur.val > num) 39 num = cur.val; 40 } 41 if (cur.t > t) 42 return num; 43 for (int i=0; i<4; i++) 44 { 45 next.x = cur.x + dir[i][0]; 46 next.y = cur.y + dir[i][1]; 47 next.z = cur.z; 48 next.val = cur.val; 49 50 if (next.x<m && next.x>=0 && next.y<n && next.y>=0) 51 { 52 next.t = cur.t + 1; 53 if (map[next.x][next.y] >= 'A' && map[next.x][next.y] <= 'Z') 54 { 55 int l = map[next.x][next.y] - 'A'; 56 if ( !((1<<l) & next.z) ) 57 { 58 next.val += va[l]; 59 next.z = (1<<l) | next.z; 60 } 61 } 62 if (!vis[next.z][next.x][next.y] && map[next.x][next.y] != '*') 63 Q.push(next), vis[next.z][next.x][next.y] = 1; 64 } 65 } 66 } 67 return num; 68 } 69 int main () 70 { 71 int c, i, j, s, l = 0, sx, sy; 72 73 scanf ("%d", &c); 74 75 while (c --) 76 { 77 scanf ("%d %d %d %d", &n, &m, &t, &s); 78 79 for (i=0; i<s; i++) 80 scanf ("%d", &va[i]); 81 82 for (i=0; i<m; i++) 83 { 84 scanf ("%s", map[i]); 85 for (j=0; j<n; j++) 86 if (map[i][j] == '@') 87 sx = i, sy = j; 88 } 89 90 num = bfs (sx, sy); 91 if (l) 92 printf (" "); 93 if (num != -1) 94 printf ("Case %d: The best score is %d. ", ++l, num); 95 else 96 printf ("Case %d: Impossible ", ++l, num); 97 } 98 99 return 0; 100 }