//开一个三维标记数组，标记Ignatius有没有以拿到钥匙的状态到达该位置
//由于钥匙的个数最多十个，所以可以用状态压缩来做
//用1和0表示有没有第i种钥匙，这样对于这个人拿到的钥匙状态就可以用二进制数表示
//用bfs找到最小值
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std ;
const int maxn = 30;
const int inf = 0x7fffffff;
int vis[maxn][maxn][1<<10];
char map[maxn][maxn] ;
int ans = ans;
struct node
{
int x , y;
int step ;
int state ;
};
int st_x , st_y ;
int n , m;
int dx[4] = {-1,0,1,0} ;
int dy[4] = {0,1,0,-1} ;
queue<struct node> que;
void bfs()
{
while(que.size())
que.pop() ;
memset(vis, 0 ,sizeof(vis)) ;
struct node first = {st_x , st_y , 0 ,0} ;
vis[st_x][st_y][0] = 1;
que.push(first) ;
while(que.size())
{
struct node now = que.front() ;
que.pop() ;
if(map[now.x][now.y] == ‘^‘)
{
ans = now.step ;
break;
}
for(int i = 0;i < 4;i++)
{
struct node next ;
next.x = now.x + dx[i] ;
next.y = now.y + dy[i] ;
if(map[next.x][next.y] == ‘*‘ || next.x < 1 || next.x > n ||next.y < 1 || next.y > m)
continue ;
if(map[next.x][next.y] >= ‘A‘ && map[next.x][next.y] <= ‘J‘)
if(!(now.state & (1<<(map[next.x][next.y] - ‘A‘))))
continue ;
if(map[next.x][next.y] >= ‘a‘ && map[next.x][next.y] <= ‘j‘)
{
next.state = now.state | (1<<(map[next.x][next.y]-‘a‘)) ;
next.step = now.step + 1;
if(vis[next.x][next.y][next.state])
continue ;
que.push(next) ;
vis[next.x][next.y][next.state] = 1;
continue;
}
next.state = now.state ;
next.step = now.step + 1;
if(vis[next.x][next.y][next.state])
continue ;
vis[next.x][next.y][next.state] = 1;
que.push(next) ;
}
}
}
int main()
{
// freopen("in.txt","r",stdin) ;
int time ;
while(scanf("%d%d%d", &n , &m , &time) != EOF)
{
for(int i = 1;i <= n;i++)
{
scanf("%s" , &map[i][1]);
for(int j = 1;j <= m;j++)
if(map[i][j] == ‘@‘)
st_x = i,st_y = j;
}
ans = inf ; //可能到不了终点，所以有可能bfs没有更新ans
bfs(); //所以ans每次都要初始化
if(ans < time)
printf("%d\n", ans);
else
printf("-1\n");
}
return 0;
}
hdu 1429 bfs+状态压缩
原文：http://blog.csdn.net/cq_pf/article/details/44680875
