題意：
? ? ?給一個(gè)n*m的矩陣，從11，走到nm，格子和格子之間可能有墻，也可能有門(mén)，有的格子上面有鑰匙，相應(yīng)的鑰匙開(kāi)相應(yīng)的們，撿鑰匙和開(kāi)門(mén)都不需要時(shí)間，問(wèn)你最少多少部能走到nm.

思路：

? ? ? ?哎！一眼就看出來(lái)了是個(gè)狀態(tài)壓縮搜索的水題，結(jié)果wa了將近兩個(gè)小時(shí)，就是因?yàn)楹雎粤艘粋€(gè)點(diǎn)可能有多把鑰匙，回來(lái)說(shuō)下這個(gè)題，我們可以開(kāi)一個(gè)數(shù)組mark[x][y][key]，表示當(dāng)前的這個(gè)點(diǎn)xy所含有的鑰匙狀態(tài)是key的時(shí)候是否走過(guò)，key是一個(gè)二進(jìn)制壓縮的數(shù)，這個(gè)很簡(jiǎn)單不解釋，同時(shí)在開(kāi)一個(gè)數(shù)組bnk[x1][y1][x2][y2]記錄從x1y1到點(diǎn)x2y2的中間是什么東西（墻，門(mén)，或者什么都沒(méi)有），然后就是遍歷就行了，題目一點(diǎn)不難，還不明白的直接看代碼就知道了。

#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; }

總結(jié)

以上是生活随笔為你收集整理的hdu4845 状态压缩BFS的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。