#include #include #include #include #include #define FOR(a,b,c) for(int a=b;a<=c;a++) #define REP(a,c) for(int a=0;a=c;a--) #define WT while(1) #define GETI(a) scanf("%d", &a) #define BZ(a) memset(a,0,sizeof(a)) #define FILL(a,b) fill(a,a+(sizeof(a)/sizeof(a[0])),b) #define FOREACH(a,b) for(__typeof((b).begin()) a=(b).begin(); a!=(b).end();a++) #define D(args...) printf(args) using namespace std; int W,H; char lines[128][128]; bool mask[128][128][16]; struct state { int s, x, y, k; state(int ss, int xx, int yy, int kk): s(ss), x(xx), y(yy), k(kk) {}; }; #include deque que; void go(int ns, int nx, int ny, int k) { char c = lines[ny][nx]; if(c=='.' || c=='X' || c=='b' || c=='y' || c=='r' || c=='g' || ((k&1)&&(c=='B')) || ((k&2)&&(c=='Y'))|| ((k&4)&&(c=='R'))|| ((k&8)&&(c=='G'))) { switch(c) { case 'b': k|=1; break; case 'y': k|=2; break; case 'r': k|=4; break; case 'g': k|=8; break; } if(mask[ny][nx][k]) return; mask[ny][nx][k] = true; que.push_back(state(ns,nx,ny,k)); } } int main() { WT { char buf[100]; fgets(buf, sizeof(buf), stdin); sscanf(buf, "%d%d", &H, &W); if(!W || !H) break; int ix, iy; REP(i, H) { fgets(lines[i], sizeof(lines[i]), stdin); lines[i][W]=0; REP(j, W) if(lines[i][j] == '*') { lines[i][j] = '.'; ix=j; iy=i; } } fgets(buf, sizeof(buf), stdin); BZ(mask); que.clear(); que.push_back(state(0, ix,iy,0)); bool found=false; while(!que.empty()) { state S = que.front(); que.pop_front(); if(lines[S.y][S.x]=='X') { printf("Escape possible in %d steps.\n", S.s); found=true; break; } if(S.x > 0) { // move left go(S.s+1, S.x-1, S.y, S.k); } if(S.x+1 < W) { // move right go(S.s+1, S.x+1, S.y, S.k); } if(S.y > 0) { // move up go(S.s+1, S.x, S.y-1, S.k); } if(S.y+1 < H) { // move down go(S.s+1, S.x, S.y+1, S.k); } } if(!found) printf("The poor student is trapped!\n"); } return 0; }