#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<vector> #include<cmath> #define INF 0x7fffffff #define eps 1e⑻ #define LL long long #define PI 3.141592654 #define CLR(a,b) memset(a,b,sizeof(a)) #define FOR(i,a,n) for(int i= a;i< n ;i++) #define FOR0(i,a,b) for(int i=a;i>=b;i--) #define pb push_back #define mp make_pair #define ft first #define sd second #define sf scanf #define pf printf #define acfun std::ios::sync_with_stdio(false) #define SIZE 100+1 using namespace std; int xx[]={0,0,⑴,1}; int yy[]={⑴,1,0,0}; int n,m; char g[SIZE][SIZE]; map<char,int>Mykey; struct lx { int x,y; int t; int key; void init(int xx,int yy,int tt,int kk) { x=xx,y=yy,t=tt,key=kk; } }start; int num[]={8,4,2,1}; bool cheack(char c,int key) { //g r y b bool unlock[4]; FOR(i,0,4) { if(key>=num[i]) { unlock[i]=1; key-=num[i]; } else unlock[i]=0; } int tmp=Mykey[c]; int ans=3; while(tmp>1) { tmp/=2; ans--; } return unlock[ans]; } void bfs() { bool vis[SIZE][SIZE][16]; CLR(vis,0); vis[start.x][start.y][start.key]=1; queue<lx>q; q.push(start); while(!q.empty()) { lx tmp=q.front(); q.pop(); //pf("%d %d time=%d ",tmp.x,tmp.y,tmp.t); if(g[tmp.x][tmp.y]=='X') { pf("Escape possible in %d steps. ",tmp.t); return; } FOR(k,0,4) { int x=tmp.x+xx[k]; int y=tmp.y+yy[k]; int key=tmp.key; if(x<0||y<0||x>=n||y>=m||g[x][y]=='#')continue; if(g[x][y]>='a'&&g[x][y]<='z'&&!cheack(g[x][y],key)) key+=Mykey[ g[x][y] ]; else if(g[x][y]>='A'&&g[x][y]<='Z'&&g[x][y]!='X') { if(!cheack(g[x][y]-'A'+'a',key))continue; } if(vis[x][y][key])continue; lx now; now.init(x,y,tmp.t+1,key); vis[x][y][key]=1; q.push(now); } } puts("The poor student is trapped!"); } int main() { Mykey['b']=1; Mykey['y']=2; Mykey['r']=4; Mykey['g']=8; while(~sf("%d%d",&n,&m),n||m) { FOR(i,0,n) { char str[SIZE]; sf("%s",str); FOR(j,0,m) { g[i][j]=str[j]; if(str[j]=='*') start.init(i,j,0,0); } } bfs(); } }