#include #include #include using namespace std; char l[110][110]; int r,c; int sx,sy; typedef pair ii; uint32_t step[110][110][16]; int dir[4][2]={{1,0}, {-1,0}, {0,1}, {0,-1}}; vector exits; void bfs() { queue q; q.push(make_pair(sx,sy)); while(!q.empty()) { ii p=q.front(); q.pop(); // printf("%d %d\n", p.first, p.second); char c=l[p.first][p.second]; if(c=='b') { for(int i=0; i<16; i++) { if(i&1) { if(step[p.first][p.second][i]>step[p.first][p.second][i&~1]) step[p.first][p.second][i]=step[p.first][p.second][i&~1]; } } } if(c=='y') { for(int i=0; i<16; i++) { if(i&2) { if(step[p.first][p.second][i]>step[p.first][p.second][i&~2]) step[p.first][p.second][i]=step[p.first][p.second][i&~2]; } } } if(c=='r') { for(int i=0; i<16; i++) { if(i&4) { if(step[p.first][p.second][i]>step[p.first][p.second][i&~4]) step[p.first][p.second][i]=step[p.first][p.second][i&~4]; } } } if(c=='g') { for(int i=0; i<16; i++) { if(i&8) { if(step[p.first][p.second][i]>step[p.first][p.second][i&~8]) step[p.first][p.second][i]=step[p.first][p.second][i&~8]; } } } /* for(int i=0; i<16; i++) for(int j=0; j<16; j++) if(i&~j && step[p.first][p.second][i]>step[p.first][p.second][j]) step[p.first][p.second][i]=step[p.first][p.second][j];*/ for(int j=0; j<4; j++) { ii n(p.first+dir[j][0], p.second+dir[j][1]); if(n.first<0 || n.second<0 || n.first>=r || n.second>=c || l[n.first][n.second]=='#') continue; bool up=false; for(int i=0; i<16; i++) { if(step[p.first][p.second][i]==0xffffffff) continue; char nc=l[n.first][n.second]; if(nc=='B') { if(!(i&1)) continue; } if(nc=='Y') { if(!(i&2)) continue; } if(nc=='R') { if(!(i&4)) continue; } if(nc=='G') { if(!(i&8)) continue; } if(step[n.first][n.second][i]>step[p.first][p.second][i]+1) { up=true; step[n.first][n.second][i]=step[p.first][p.second][i]+1; } } if(up) q.push(n); } } uint32_t m=0xffffffff; for(vector::iterator i=exits.begin(); i!=exits.end(); ++i) { for(int j=0; j<16; j++) { if(step[i->first][i->second][j]first][i->second][j]; } } if(m==0xffffffff) { puts("The poor student is trapped!"); } else { printf("Escape possible in %d steps.\n", m); } } int main() { while(scanf("%d %d", &r, &c), r || c) { gets(l[0]); bool exit=false; exits.clear(); for(int i=0; i