给你一个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 " ,BFS(sx ,sy)); } return 0; }