#include #include using namespace std; #define duzo 2000000 int c[20][104][104]; char t[104][104]; int klucz[4]={1,2,4,8}; int n,m,start[2],end[2]; struct asd { int x,y,odl,stan; };asd tmp; queue Q; int bfs() { int x, y, odl, stan; while(!Q.empty()) { tmp=Q.front(); Q.pop(); x=tmp.x; y=tmp.y; odl=tmp.odl; stan=tmp.stan; // if (x!=0 && y!=0 && x!=2) if (c[stan][x][y]<=odl) continue; c[stan][x][y]=odl; // printf("ASD"); switch (t[x][y]) { case 'b': stan |= klucz[0]; break; case 'y': stan |= klucz[1]; break; case 'r': stan |= klucz[2]; break; case 'g': stan |= klucz[3]; break; case 'B': if ((stan&klucz[0]) == 0) goto blok; break; case 'Y': if ((stan&klucz[1]) == 0) goto blok; break; case 'R': if ((stan&klucz[2]) == 0) { goto blok; } break; case 'G': if ((stan&klucz[3]) == 0) goto blok; break; case 'X': printf("Escape possible in %d steps.\n",odl); return 0; case '#': goto blok; } // printf("%d %d - %d\n",x,y,stan); tmp.x=x-1; tmp.y=y; tmp.odl=odl+1; tmp.stan=stan; // if (c[stan][tmp.x][tmp.y]>tmp.odl) Q.push(tmp); tmp.x+=2; // if (c[stan][tmp.x][tmp.y]>tmp.odl) Q.push(tmp); tmp.x--; tmp.y--; // if (c[stan][tmp.x][tmp.y]>tmp.odl) Q.push(tmp); tmp.y+=2; // if (c[stan][tmp.x][tmp.y]>tmp.odl) Q.push(tmp); blok:; } printf("The poor student is trapped!\n"); return 0; } int main() { while(1) { scanf("%d %d\n",&n,&m); if (n==0) return 0; for (int i=0; i<=n+1; i++) t[0][i]=t[i][0]=t[n+1][i]=t[i][n+1]='#'; for (int i=1; i<=n; i++) { scanf("%s\n",t[i]+1); // printf("%s\n"); } // getchar(); end[0]=end[1]=0; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) { // printf("%d %d %c\n",i,j,t[i][j]); for (int k=0; k<=16; k++) c[k][i][j]=duzo; if (t[i][j]=='X') { end[0]=i; end[1]=j; } else if (t[i][j]=='*') { // printf("ASD"); start[0]=i; start[1]=j; } } // printf("%d %d\n",start[0],start[1]); if (end[0]==0) printf("The poor student is trapped!\n"); else { tmp.x=start[0]; tmp.y=start[1]; tmp.odl=tmp.stan=0; while(!Q.empty()) Q.pop(); Q.push(tmp); bfs(); } // return 0; } }