1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5  6 int n , m; 7 const int size = 110; 8 int dir[4][2] = {1,0,-1,0,0,1,0,-1}; 9 char mp[size][size];10 int kk[size][size];11 bool vis[size][size][1<<6];12 struct node13 {14     int x , y , key , T;15     node(){};16     node( int u , int v , int w , int p ):x(u),y(v),key(w),T(p){};17 };18 queue<node> q;19 20 void init( )21 {22     memset( kk , 0 , sizeof(kk) );23     memset( vis , false, sizeof(vis) );24     while( !q.empty() )25         q.pop();26 }27 28 int bfs( int stx , int sty )29 {30     q.push( node( stx , sty , kk[stx][sty] , 0 ) );31     vis[stx][sty][ kk[stx][sty] ] = true;32     while( !q.empty() )33     {34         node now = q.front();35         q.pop();36         //cout << "x: " << now.x << " y: " << now.y << " T: " << now.T << endl;37         if( mp[ now.x ][ now.y ] == ‘X‘ )38             return now.T;39         for( int i = 0 ; i<4 ; i++ )40         {41             int xx = now.x + dir[i][0];42             int yy = now.y + dir[i][1];43             int KEY = now.key | kk[ xx ][ yy ];44             if( xx>=0 && xx<n && yy>=0 && yy<m && mp[xx][yy]!=‘#‘ && !vis[xx][yy][KEY] )45             {46                 if( mp[xx][yy]==‘B‘ && ( (now.key&2)==0) )47                     continue;48                 else if( mp[xx][yy]==‘Y‘ && ( (now.key&4)==0) )49                     continue;50                 else if( mp[xx][yy]==‘R‘ && ( (now.key&8)==0) )51                     continue;52                 else if( mp[xx][yy]==‘G‘ && ( (now.key&16)==0) )53                     continue;54                 q.push( node(xx,yy,KEY,now.T+1) );55                 vis[xx][yy][KEY] = true;56             }57         }58     }59     return -1;60 }61 62 int main()63 {64     cin.sync_with_stdio(false);65     int ans , stx , sty;66     while( cin >> n >> m &&(n||m) )67     {68         init();69         for( int i = 0 ; i<n ; i++ )70         {71             cin >> mp[i];72         }73         for( int i = 0 ; i<n ; i++ )74         {75             for( int j = 0 ; j<m ; j++ )76             {77                 if( mp[i][j]==‘*‘ )78                 {79                     stx = i;80                     sty = j;81                 }82                 else if( mp[i][j]==‘b‘ )83                     kk[i][j] |= (1<<1);84                 else if( mp[i][j]==‘y‘ )85                     kk[i][j] |= (1<<2);86                 else if( mp[i][j]==‘r‘ )87                     kk[i][j] |= (1<<3);88                 else if( mp[i][j]==‘g‘ )89                     kk[i][j] |= (1<<4);90             }91         }92         ans = bfs( stx , sty );93         if( ans==-1 )94             cout << "The poor student is trapped!" << endl;95         else96             cout << "Escape possible in " << ans << " steps." << endl;97     }98     return 0;99 }