/* BFS：二进制状态压缩 */ #include <stdio.h> #include <string.h> #include <stdlib.h> #include <limits.h> #include <malloc.h> #include <ctype.h> #include <math.h> #include <string> #include <iostream> #include <algorithm> using namespace std; #define MAXN 11111 #include<queue> const int INF = 999999; struct node { int x,y,step; int key; }; queue<node> q; int n,m,time; char mp[105][105]; bool vis[105][105][20]; int xx[4]={1,-1,0,0}; int yy[4]={0,0,1,-1}; int bfs(int x,int y) { node from,next; from.x=x,from.y=y,from.key=0,from.step=0; vis[x][y][0]=1; q.push (from); while(!q.empty ()) { from=q.front (); q.pop (); for(int i=0;i<4;i++) { int dx=from.x+xx[i]; int dy=from.y+yy[i]; if(dx>=0&&dx<n&&dy>=0&&dy<m&&vis[dx][dy][from.key]==0&&mp[dx][dy]!='#') { next.x=dx,next.y=dy,next.step=from.step+1; if(mp[dx][dy]=='X') return from.step+1; else if(mp[dx][dy]>='a'&&mp[dx][dy]<='d')//find the key { next.key=from.key|(1<<(mp[dx][dy]-'a')); vis[dx][dy][from.key]=1; q.push (next); } else if(mp[dx][dy]>='A'&&mp[dx][dy]<='D')//find the door { if(from.key&(1<<(mp[dx][dy]-'A'))) { next.key=from.key; vis[dx][dy][from.key]=1; q.push (next); } } else { vis[dx][dy][from.key]=1; next.key=from.key; q.push (next); } } } } return -1; } int main() { int i,j; int x,y; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; memset(mp,0,sizeof(mp)); memset(vis,0,sizeof(vis)); while(!q.empty ()) q.pop (); for(i=0;i<n;i++) { scanf("%s",mp[i]); for(j=0;j<m;j++) { if(mp[i][j]=='*') x=i,y=j; if(mp[i][j]=='B') mp[i][j]='A'; if(mp[i][j]=='Y') mp[i][j]='B'; if(mp[i][j]=='R') mp[i][j]='C'; if(mp[i][j]=='G') mp[i][j]='D'; if(mp[i][j]=='b') mp[i][j]='a'; if(mp[i][j]=='y') mp[i][j]='b'; if(mp[i][j]=='r') mp[i][j]='c'; if(mp[i][j]=='g') mp[i][j]='d'; } } int ans=bfs(x,y); if(ans==-1) printf("The poor student is trapped! "); else printf("Escape possible in %d steps. ",ans); } return 0; }