http://acm.hdu.edu.cn/showproblem.php?pid=1885
再贴一个链接http://blog.csdn.net/u013081425/article/details/21756237
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#define LL long long
#define _LL __int64 using namespace std;
const int INF = 0x3f3f3f3f; int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
struct node
{
int x,y;
int sta;
int step;
}; int n,m;
int sx,sy;
char map[110][110];
int mark[110][110][(1<<4)+10]; queue <struct node>que; int ans; int small(char ch)
{
if(ch == 'b')
return 0;
else if(ch == 'y')
return 1;
else if(ch == 'r')
return 2;
else if(ch == 'g')
return 3;
} int big(char ch)
{
if(ch == 'B')
return 0;
else if(ch == 'Y')
return 1;
else if(ch == 'R')
return 2;
else if(ch == 'G')
return 3;
} void bfs()
{
while(!que.empty()) que.pop();
memset(mark,0,sizeof(mark)); mark[sx][sy][0] = 1;
que.push((struct node) {sx,sy,0,0}); while(!que.empty())
{
struct node u = que.front();
que.pop();
if(map[u.x][u.y] == 'X')
{
ans = u.step;
return;
} for(int d = 0; d < 4; d++)
{
int x = u.x + dir[d][0];
int y = u.y + dir[d][1];
int sta = u.sta; if(x < 1 || x > n || y < 1 || y > m) continue; if(map[x][y] == '.' || map[x][y] == '*' || map[x][y] == 'X') //注意出口‘X’也要进队列
{
if(!mark[x][y][sta])
{
mark[x][y][sta] = 1;
que.push((struct node){x,y,sta,u.step+1});
}
}
else if(map[x][y] >= 'a' && map[x][y] <= 'z')
{
int add = small(map[x][y]); if((sta&(1<<add)) == 0)
sta += (1 << add);
if(!mark[x][y][sta])
{
mark[x][y][sta] = 1;
que.push((struct node){x,y,sta,u.step+1});
}
}
else if(map[x][y] >= 'A' && map[x][y] <= 'Z')
{
int add = big(map[x][y]);
if( (sta&(1<<add)) && !mark[x][y][sta] )
{
mark[x][y][sta] = 1;
que.push((struct node){x,y,sta,u.step+1});
}
}
}
}
} int main()
{
while(~scanf("%d %d",&n,&m))
{
if(n == 0 && m == 0) break;
for(int i = 1; i <= n; i++)
{
scanf("%s",map[i]+1);
for(int j = 1; j <= m; j++)
{
if(map[i][j] == '*')
{
sx = i;
sy = j;
}
}
} ans = -1;
bfs();
if(ans == -1)
printf("The poor student is trapped!\n");
else printf("Escape possible in %d steps.\n",ans);
}
return 0;
}