//{{{ #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define FOR(I,A,B) for(int I=(A);I<(B);I++) #define FORD(I,A,B) for(int I=(A);I>=(B);I--) #define REP(I,N) for(int I=0;I<(N);I++) #define VAR(V,init) __typeof(init) V=(init) #define FOREACH(I,C) for(VAR(I,(C).begin());I!=(C).end();I++) #define CLR(A,v) memset((A),v,sizeof((A))) #define ALL(X) (X).begin(), (X).end() #define PB push_back #define MP make_pair #define FI first #define SE second //}}} const int DX[]={0,1,0,-1}, DY[]={1,0,-1,0}; int w,h; char M[102][102]; int T[16][102][102]; int ZN[500]; const int nmx=1000000; int cango(int x,int y,int mask) { if (x< 0 || x>=w || y<0 || y>=h) return -1; if (M[y][x]=='#') return -1; if ( toupper(M[y][x]) == M[y][x] ) if ( (mask&(ZN[(int)M[y][x]]))!=(ZN[(int)M[y][x]])) return -1; return ZN[(int)M[y][x]]; } int go(int x,int y) { static int X[nmx],Y[nmx],MS[nmx]; int h=0,t=0; X[t]=x; Y[t]=y; MS[t]=0; T[0][y][x]=0; t++; int nms,ms,tx,ty,tmp; while (h < t) { y=Y[h]; x=X[h]; ms=MS[h++]; // printf("x:%d y:%d ms:%d %d\n",x,y,ms,T[ms][y][x]); if (M[y][x]=='X') return T[ms][y][x]; REP(d,4) { tx=DX[d]+x; ty=DY[d]+y; tmp=cango(tx,ty,ms); // printf("tx:%d ty:%d tmp:%d\n",tx,ty,tmp); if (tmp == -1) continue; nms=ms|tmp; if (T[nms][ty][tx]!=-1) continue; T[nms][ty][tx]=T[ms][y][x]+1; X[t]=tx; Y[t]=ty; MS[t]=nms; t++; } } return -1; } int main() { CLR(ZN,0); ZN[(int)'b']=1; ZN[(int)'B']=1; ZN[(int)'y']=2; ZN[(int)'Y']=2; ZN[(int)'R']=4; ZN[(int)'r']=4; ZN[(int)'g']=8; ZN[(int)'G']=8; for(;;) { scanf("%d%d",&h,&w); if (h==0 && w==0) break; REP(y,h) scanf("%s",M[y]); CLR(T,-1); int bx=0,by=0; REP(y,h) REP(x,w) if (M[y][x]=='*') { by=y; bx=x; break; } int res=go(bx,by); if (res==-1) printf("The poor student is trapped!\n"); else printf("Escape possible in %d steps.\n",res); } return 0; }