题意 ： 出口不止一个，一共有四种颜色不同的门由大写字母表示，而钥匙则是对应的小写字母，当你走到门前边的位置时，如果你已经走过相应的钥匙的位置这个门就可以走，只要获得一把钥匙就可以开所有同颜色的门。问你能不能走出来。
思路 ： 这个题比赛的时候完全没有思路，想了好久脑子都疼了也没想出来。原来是一个三维的BFS，因为要拿钥匙的缘故可能有些地方要来回走，所以不能像以前标记二维一样只要走过的点就不能走了，这里用三维来标记，你要是走过这个地方并且钥匙数都是一样的，那就不用再走了，因为那代表你又走回来了，看了网上大神写的学到了一个新的表示钥匙的方法，按位与，要不就要用数组什么的太麻烦。
//HDU 1885
#include <stdio.h>
#include <string.h>
#include <queue>
#include <string>
#include <iostream> using namespace std ; struct node
{
int x,y,step ;
int keys ;
} p[],temp,temp1 ; int n,m ;
int key[] = {'b','y','r','g'} ;
int door[] = {'B','Y','R','G'} ;
int dir[][] = {{,-},{,},{-,},{,}} ;
bool vis[][][( << ) + ] ;
char mapp[][] ; void BFS(int sx,int sy)
{
queue<node>Q ;
temp.x = sx ;
temp.y = sy ;
temp.step = temp.keys = ;
Q.push(temp) ;
vis[sx][sy][] = true ;
while(!Q.empty())
{
temp = Q.front() ;
Q.pop() ;
if(mapp[temp.x][temp.y] == 'X')
{
printf("Escape possible in %d steps.\n",temp.step) ;
return ;
}
for(int i = ; i < ; i++)
{
temp1.x = temp.x + dir[i][] ;
temp1.y = temp.y + dir[i][] ;
temp1.step = temp.step+;
temp1.keys = temp.keys ; if(mapp[temp1.x][temp1.y] == '#' || temp1.x < || temp1.x >= n || temp1.y < || temp1.y >= m)
continue ;
else if(islower(mapp[temp1.x][temp1.y]))
{
for(int k = ; k < ; k++)
{
if(mapp[temp1.x][temp1.y] == key[k])
{
if((temp1.keys & ( << k)) == )//如果这把钥匙没有，就加上。
temp1.keys += ( << k) ; }
if(!vis[temp1.x][temp1.y][temp1.keys])
{
Q.push(temp1) ;
vis[temp1.x][temp1.y][temp1.keys] = true ;
//break ;
}
}
}
else if(isupper(mapp[temp1.x][temp1.y]) && mapp[temp1.x][temp1.y] != 'X')
{
for(int k = ; k < ; k++)
{
if(mapp[temp1.x][temp1.y] == door[k])
{
if(temp1.keys & ( << k))
{
if(!vis[temp1.x][temp1.y][temp1.keys])
{
vis[temp1.x][temp1.y][temp1.keys] = true ;
Q.push(temp1) ; }
break ;
}
}
}
}
else
{
if(!vis[temp1.x][temp1.y][temp1.keys])
{
vis[temp1.x][temp1.y][temp1.keys] = true ;
Q.push(temp1) ;
}
}
}
}
printf("The poor student is trapped!\n") ;
} int main()
{
int sx,sy ;
while(~scanf("%d %d",&n,&m))
{
if(n == && m == ) break ;
for(int i = ; i < n ; i++)
scanf("%s",mapp[i]) ;
memset(vis,false,sizeof(vis)) ;
for(int i = ; i < n ; i++)
{
for(int j = ; j < m ; j++)
{
if(mapp[i][j] == '*')
{
sx = i ;
sy = j ;
}
}
}
BFS(sx,sy) ;
}
return ;
}