题目：http://acm.hdu.edu.cn/showproblem.php?pid=1885
题目意思：给出一个n*m的迷宫，各种字符的含义可以参考题目所给的表格，移动只能往上下左右，问能否从*出发到达X，*只有一个，但X可能有多个，如果能，输出最少步数，不能则要输出另一句信息。
还是比较经典的迷宫题目，只是在这个基础上加上了门和钥匙，所以在搜索的时候要记录上钥匙的状态。由于门最多4种，所以可以用4个二进制位来表示是否带有对应的钥匙，所以钥匙的状态有2^4=16种，地图100*100，所以总状态数最多160000。采用广搜写法，细心点码就能AC。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct Point{
int x, y, s, u;
}p;
int xl[4]={-1,1,0,0};
int yl[4]={0,0,-1,1};
int n, m, i, j, x, y, a, b;
char map[100][110];
bool vis[100][100][1<<4];
int idx(char ch){
if(ch=='b') return 0;
if(ch=='y') return 1;
if(ch=='r') return 2;
return 3;
}
int main(){
while(~scanf("%d %d", &n, &m) && (n||m)){
memset(vis,0,sizeof(vis));
for(i=0; i<n; i++){
scanf("%s", map[i]);
for(j=0; j<m; j++){
if(map[i][j]=='*'){
x=i; y=j;
break;
}
}
}
queue<Point> Q;
Q.push((Point){x,y,0,0});
vis[x][y][0]=1;
bool flag=0;
while(!Q.empty()){
p=Q.front();Q.pop();
x=p.x; y=p.y; p.u++;
for(i=0; i<4; i++){
a = x+xl[i];
b = y+yl[i];
if(a<0 || a>=n || b<0 || b>=m) continue;
if(map[a][b]=='X'){
printf("Escape possible in %d steps.\n", p.u);
flag=1;
break;
}
if(map[a][b]=='#') continue;
if(map[a][b]>='A' && map[a][b]<='Z'){
j = idx(map[a][b]-'A'+'a');
if(!(p.s&(1<<j))) continue;
j = p.s;
}
else if(map[a][b]>='a' && map[a][b]<='z'){
j = idx(map[a][b]);
j = p.s | (1<<j);
}
else j=p.s;
if(vis[a][b][j]) continue;
vis[a][b][j]=1;
Q.push((Point){a,b,j,p.u});
}
if(flag) break;
}
if(!flag) puts("The poor student is trapped!");
}
return 0;
}