題意：
? ? ?給一個n*m的矩陣，從11，走到nm，格子和格子之間可能有墻，也可能有門，有的格子上面有鑰匙，相應的鑰匙開相應的們，撿鑰匙和開門都不需要時間，問你最少多少部能走到nm.

思路：

? ? ? ?哎！一眼就看出來了是個狀態壓縮搜索的水題，結果wa了將近兩個小時，就是因為忽略了一個點可能有多把鑰匙，回來說下這個題，我們可以開一個數組mark[x][y][key]，表示當前的這個點xy所含有的鑰匙狀態是key的時候是否走過，key是一個二進制壓縮的數，這個很簡單不解釋，同時在開一個數組bnk[x1][y1][x2][y2]記錄從x1y1到點x2y2的中間是什么東西（墻，門，或者什么都沒有），然后就是遍歷就行了，題目一點不難，還不明白的直接看代碼就知道了。

#include<stdio.h> #include<string.h> #include<queue>#define N 20 using namespace std;typedef struct {int x ,y ,t ,key; }NODE;NODE xin ,tou; int mark[N][N][1<<10+1]; int bank[N][N][N][N]; int map[N][N]; int dir[4][2] = {0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0};int BFS(int n ,int m) {memset(mark ,0 ,sizeof(mark));xin.x = xin.y = 1;xin.t = 0;xin.key = 0 | map[1][1];mark[xin.x][xin.y][xin.key] = 1;queue<NODE>q;q.push(xin);while(!q.empty()){tou = q.front();q.pop();for(int i = 0 ;i < 4 ;i ++){xin.x = tou.x + dir[i][0];xin.y = tou.y + dir[i][1];xin.t = tou.t + 1;if(xin.x < 1 || xin.x > n || xin.y < 1 || xin.y > m)continue;if(!bank[tou.x][tou.y][xin.x][xin.y]) continue;if(bank[tou.x][tou.y][xin.x][xin.y] == -1 || tou.key & (1 << (bank[tou.x][tou.y][xin.x][xin.y] - 1))){if(!map[xin.x][xin.y]) xin.key = tou.key;else xin.key = tou.key | map[xin.x][xin.y];if(!mark[xin.x][xin.y][xin.key]){mark[xin.x][xin.y][xin.key] = 1;q.push(xin);if(xin.x == n && xin.y == m) return xin.t;}}}}return -1; }int main () {int n ,m ,p ,k ,q ,i;int x1 ,x2 ,y1 ,y2 ,key;while(~scanf("%d %d %d" ,&n ,&m ,&p)){scanf("%d" ,&k);memset(bank ,255 ,sizeof(bank));for(i = 1 ;i <= k ;i ++){scanf("%d %d %d %d %d" ,&x1 ,&y1 ,&x2 ,&y2 ,&key);bank[x1][y1][x2][y2] = bank[x2][y2][x1][y1] = key;}scanf("%d" ,&q);memset(map ,0 ,sizeof(map));for(i = 1 ;i <= q ;i ++){scanf("%d %d %d" ,&x1 ,&y1 ,&key);map[x1][y1] |= (1 << (key - 1));}printf("%d\n" ,BFS(n ,m));}return 0; }

總結

以上是生活随笔為你收集整理的hdu4845 状态压缩BFS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。