題意：
? ? ?給你一個n*m的地圖，問你從起點出發，吧所有的寶藏都撿完用的最少時間。

思路：k <= 4,水題，直接開一個數組mark[now][x][y];now代表的是當前檢寶藏的二進制壓縮狀態，然后就直接搜索就行了。

#include<stdio.h> #include<string.h> #include<queue>#define N 100 + 5 using namespace std;typedef struct {int x ,y ,now; }NODE;NODE xin ,tou; int mark[1<<4][N][N]; int map[N][N]; int dir[4][2] = {0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0}; NODE K[5]; int n ,m ,k;bool ok(int x ,int y ,int now) {return x <= n && x >= 1 && y <= m && y >= 1 && !mark[now][x][y] && map[x][y]; }int BFS(int sx ,int sy) {queue<NODE>q;xin.x = sx ,xin.y = sy ,xin.now = 0;int mk = 0;for(int i = 1 ;i <= k ;i ++)if(xin.x == K[i].x && xin.y == K[i].y){mk = i;break;}if(mk) xin.now = 0 | (1 << (mk - 1)); memset(mark ,0 ,sizeof(mark));q.push(xin);mark[xin.now][xin.x][xin.y] = 1;while(!q.empty()){tou = q.front();q.pop();if(tou.now == (1<<k) - 1)return mark[tou.now][tou.x][tou.y] - 1;for(int i = 0 ;i < 4 ;i ++){xin.x = tou.x + dir[i][0];xin.y = tou.y + dir[i][1];xin.now = tou.now;int mk = 0;for(int j = 1 ;j <= k ;j ++)if(xin.x == K[j].x && xin.y == K[j].y){mk = j;break;}if(mk) xin.now = tou.now | (1<<(mk - 1));if(ok(xin.x ,xin.y ,xin.now)){mark[xin.now][xin.x][xin.y] = mark[tou.now][tou.x][tou.y] + 1;q.push(xin);}}}return -1; }int main () {int i ,j ,sx ,sy;char str[N];while(~scanf("%d %d" ,&n ,&m) && n + m){for(i = 1 ;i <= n ;i ++){scanf("%s" ,str);for(j = 1 ;j <= m ;j ++){if(str[j-1] == '@')map[i][j] = 1 ,sx = i ,sy = j;if(str[j-1] == '.') map[i][j] = 1;if(str[j-1] == '#') map[i][j] = 0;}}scanf("%d" ,&k);for(i = 1 ;i <= k ;i ++)scanf("%d %d" ,&K[i].x ,&K[i].y);printf("%d\n" ,BFS(sx ,sy));}return 0; }

總結

以上是生活随笔為你收集整理的hdu4771 水搜索（状态压缩+bfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

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