选拔赛(2)简单的状态压缩+bfs
屌洋直接用8维数组过的...代码美的一逼
题意：
悟空(K)找唐僧(T)，只能上下左右四个方向走，每步花费一个时间，碰到蛇精(S)需要额外花费一个时间去消灭，需要按照顺序(1, 2 ... k)搜集K把钥匙才能打开唐僧所在的房间。
总结：
在读入矩阵的时候，把每个S换成其他的字符，比如(a, b, c...)，这样再bfs的时候，碰到蛇精所在房间就可以直接判断当前蛇是否已经被杀死
任何题目中bfs的时候不能修改原有的矩阵数据，(后来的节点还会走到这个点上)
if(a & b == 0){...} if((a&b) == 0){...}
下面的表达式才能正确判断，运算符优先级(可以在任何时候都把位运算放在括号里面)
1 #include <bits/stdc++.h> 2 3 const int MAXN = 100+5; 4 5 int n, k; 6 char ma[MAXN][MAXN]; 7 // state compression 8 // the binary format of 31 is 11111 9 // there are at most 5 snakes in the maze 10 // so just use a binary digit bit to mark 11 // weather it has been visited or not 12 // e.g. when wukong kills sankes numbered 1, 2, 5 13 // the statement will be 10011(19) 14 15 bool vis[MAXN][MAXN][10][32]; 16 17 // for direction Wukong can go 18 int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}}; 19 20 struct QueNode 21 { 22 int x, y, k, s, t; 23 QueNode(){} 24 // k is the number of keys wukong has 25 // s is the states of snakes (detail is the descriptioni of 'vis' above ) 26 // t is the time 27 QueNode(int _x, int _y, int _k, int _s, int _t):x(_x), y(_y), k(_k), s(_s), t(_t){} 28 29 }; 30 31 std::queue<QueNode> que; 32 33 int main() 34 { 35 36 // this code below will clutter the output 37 /* std::ios::sync_with_stdio(false); */ 38 39 while(std::cin >> n >> k && (n||k)){ 40 41 // init the variable 42 // the efficient way to clear a std::queue 43 // just create a empty_que and swap it with original queue 44 memset(ma, '#', sizeof ma); 45 memset(vis, false, sizeof vis); 46 std::queue<QueNode> empty_que; 47 std::swap(que, empty_que); 48 49 // the highlight point 50 // dealing with the snakes 51 // rename it to enable it to show which snake it is 52 int snake_num = 0; 53 54 for(int i = 1; i <= n; ++ i){ 55 for(int j = 1; j <= n; ++ j){ 56 std::cin >> ma[i][j]; 57 if(ma[i][j] == 'S'){ 58 ma[i][j] = (++snake_num) + 'a'; 59 } 60 if(ma[i][j] == 'K'){ 61 que.push(QueNode(i, j, 0, 0, 0)); 62 vis[i][j][0][0] = true; 63 } 64 } 65 } 66 67 bool ok = false; 68 69 while(que.empty() == false){ 70 QueNode u = que.front(); 71 que.pop(); 72 // while wukong reaches the room in which Monk tang is 73 // and wukong has enough keys 74 if(ma[u.x][u.y] == 'T' && u.k == k){ 75 std::cout << u.t << std::endl; 76 ok = true; 77 break; 78 } 79 // if wukong enter the room with snake and has not killed the snake 80 // it takes 1 minute to kill it 81 if(ma[u.x][u.y] <= 'a'+5 && ma[u.x][u.y] >= 'a'+1){ 82 int num = 1<<(ma[u.x][u.y] -'a'-1); 83 84 /* if( u.s & num == 0) */ 85 // the statement above is wrong 86 // pay attention to operator precedence 87 if( (u.s&num) == 0){ 88 u.s |= num; 89 ++ u.t; 90 que.push(u); 91 vis[u.x][u.y][u.k][u.s] = true; 92 continue; 93 } 94 } 95 96 for(int i = 0; i < 4; ++ i){ 97 QueNode v(u); 98 ++ v.t; 99 v.x += dir[i][0]; 100 v.y += dir[i][1]; 101 102 if(ma[v.x][v.y] != '#'){ 103 if(ma[v.x][v.y] - '0' == u.k + 1){ 104 v.k = u.k + 1; 105 } 106 if(vis[v.x][v.y][v.k][v.s] == false){ 107 vis[v.x][v.y][v.k][v.s] = true; 108 que.push(v); 109 } 110 } 111 } 112 113 } 114 if(ok == false){ 115 puts("impossible"); 116 } 117 118 } 119 120 }