#include #include #include #include #include #include #include using namespace std; #define PRINTF(args...) printf(args) //#define PRINTF(args...) #define FOR(i,a,b) for(int i=(a); i<(int)(b); ++i) #define FORD(i,a,b) for(int i=(a)-1; i>=(int)(b); --i) #define FOREACH(i,C) for(__typeof(C.begin()) i=C.begin(); i!=C.end(); ++i) struct el { int x, y, b, yy, r, g; el(int tx = 0, int ty = 0):x(tx),y(ty),b(0),yy(0),r(0),g(0){} }; int n, m, sx, sy, dp[105][105][2][2][2][2]; int dx[] = {-1, 0, 0, 1}; int dy[] = { 0,-1, 1, 0}; char tab[105][105]; queue kol; bool testcase() { scanf("%d %d",&n,&m); if(n == 0 && m == 0) return false; for(int i = 0; i < n; ++i) { scanf("%s", tab + i); for(int j = 0; j < m; ++j) { if(tab[i][j] == '*') { sx = i; sy = j; tab[i][j] = '.'; } } } while(!kol.empty()) kol.pop(); memset(dp,-1,sizeof(dp)); dp[sx][sy][0][0][0][0] = 0; kol.push(el(sx,sy)); int best = -1; while(!kol.empty()) { el akt = kol.front(); kol.pop(); int x = akt.x, y = akt.y, b = akt.b, yy = akt.yy, r = akt.r, g = akt.g; int odl = dp[x][y][b][yy][r][g]; if(tab[x][y] == 'X') { best = odl; break; } for(int i = 0; i < 4; ++i) { int nx = x + dx[i], ny = y + dy[i]; el nakt = akt; nakt.x = nx; nakt.y = ny; if(nx < 0 || nx >= n || ny < 0 || ny >= m || tab[nx][ny] == '#') continue; if(tab[nx][ny] == 'B' && b == 0) continue; if(tab[nx][ny] == 'Y' && yy == 0) continue; if(tab[nx][ny] == 'R' && r == 0) continue; if(tab[nx][ny] == 'G' && g == 0) continue; if(tab[nx][ny] == 'b') nakt.b = 1; if(tab[nx][ny] == 'y') nakt.yy = 1; if(tab[nx][ny] == 'r') nakt.r = 1; if(tab[nx][ny] == 'g') nakt.g = 1; if(dp[nx][ny][nakt.b][nakt.yy][nakt.r][nakt.g] != -1) continue; dp[nx][ny][nakt.b][nakt.yy][nakt.r][nakt.g] = odl + 1; kol.push(nakt); } } if(best >= 0) printf("Escape possible in %d steps.\n", best); else printf("The poor student is trapped!\n"); return true; } int main() { while(testcase()); return 0; }