让我初识位压缩的一道BFS题，之前采用结构中增加char类型的key[26]，然后采用数组映射实现对钥匙的存储，交上去悲剧地MLE了，然后在YHL大牛的博客上发现了位压缩这一好东东，现在和大家分享一下：用二进制来表示手头的钥匙有哪些，100表示有第三把钥匙，111表示有第三、二、一把，搜索下一点时，如果该点为钥匙点，则可采用|运算来模拟拾取，显然0001 | 1000 = 1001，同理，当为相应的门时采用&运算来模拟开启，例如1101 & 0001 = 0001（即可以打开'A'门），附AC代码如下：
# include<iostream># include<queue>using namespace std;struct Node{ int x, y; int time; int nkey; };int n, m, t;int Go[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};int map[25][25];int visited[25][25][1025];int sx, sy, ex, ey;int check(int x, int y){ if (x >=1 && x <= n && y >= 1 && y <= m )return 1; return 0;}int check1;void Bfs(){ queue<Node> Que; memset(visited, 0, sizeof(visited)); Node temp; temp.x = sx; temp.y = sy; temp.nkey = 0; visited[temp.x][temp.y][temp.nkey] = 1; temp.time = 0; Que.push(temp); while (!Que.empty()){ Node pre = Que.front(); Que.pop(); if (pre.x == ex && pre.y == ey && pre.time < t){ check1 = pre.time; return ; } for (int i = 0; i < 4; i ++){ Node next; next.x = pre.x + Go[i][0]; next.y = pre.y + Go[i][1]; next.nkey = pre.nkey; next.time = pre.time; if (check(next.x, next.y) && map[next.x][next.y]!= '*'){ next.time ++; if (next.time > t)continue; if (map[next.x][next.y] >= 'a' && map[next.x][next.y] <= 'z'){ int key = (1<<(map[next.x][next.y] - 'a'));//左移一位，因为0000的意思应该是0001； next.nkey |= key;//拾取钥匙 if (!visited[next.x][next.y][next.nkey]){ visited[next.x][next.y][next.nkey] = 1; Que.push(next); } } else if (map[next.x][next.y] >= 'A' && map[next.x][next.y] <= 'Z'){ int key = (map[next.x][next.y] - 'A'); if ((next.nkey>>key)&1 && !visited[next.x][next.y][next.nkey]){//右移key位后与1，判断是不是存在打开当前
//门的钥匙 visited[next.x][next.y][next.nkey] = 1; Que.push(next); } } else if (!visited[next.x][next.y][next.nkey]){//这里没想太清楚，以后补充，貌似是表示走过的点不能再重新走，除非
//拿或者用过了钥匙 visited[next.x][next.y][next.nkey] = 1; Que.push(next); } } } }}int main(){ while (EOF != scanf("%d %d %d", &n, &m, &t)){ for (int i = 1; i <= n; i ++){ getchar(); for (int j = 1; j <= m; j ++){ scanf("%c",&map[i][j]); if (map[i][j] == '@'){sx = i; sy = j;} if (map[i][j] == '^'){ex = i; ey = j;} } } check1 = -1; Bfs(); printf("%d/n", check1); } return 0; }
