TOJ 449

//TOJ
#include <bits/stdc++.h>
using namespace std;

int toNum(char c){
    if(c == '.' || c == '*')return 0;
    if(c == '#')return 1;
    if(c == 'R')return 2;
    if(c == 'G')return 3;
    if(c == 'B')return 4;
    if(c == 'Y')return 5;
    if(c == 'X')return -1;
    return -toNum(c-32);
}

int maze[100][100];
bool vis[100][100][1<<6];

struct stat{
    int x, y;
    int key = 0;
    int step = 0;
};

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

int32_t main(){
    int n,m;
    char c;
    stat one;
    cin >> n >> m;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin >> c;
            if(c == '*'){
                one.x = i;
                one.y = j;
            }
            maze[i][j]= toNum(c);
        }
    }
    deque<stat> dq;
    dq.emplace_back(one);
    int ans = -1;
    while(!dq.empty() && ans == -1){
        stat tmd = dq.front();
        dq.pop_front();
        //cout << tmd.x << ' ' << tmd.y << ' ' << tmd.key << ' ' <<  tmd.step << '\n';
        for(int i = 0; i < 4; ++i){
            int nx = tmd.x + dx[i];
            int ny = tmd.y + dy[i];
            if(!(0 <= nx && nx < n && 0 <= ny && ny < m))continue;
            if(maze[nx][ny] >= 1 && !(tmd.key & (1<<maze[nx][ny])))continue;
            //cout << ' ' << nx << ' ' << ny << '\n';
            if(maze[nx][ny] == -1){
                ans = tmd.step+1;
                break;
            }
            stat nxt = {.x = nx, .y = ny, .key = tmd.key, .step = tmd.step+1};
            if(maze[nx][ny] <= -2)nxt.key |= (1<<-maze[nx][ny]);
            //cout << ' ' << nxt.x << ' ' << nxt.y << ' ' << nxt.key << '\n';
            if(vis[nxt.x][nxt.y][nxt.key])continue;
            vis[nxt.x][nxt.y][nxt.key] = 1;
            dq.emplace_back(nxt);
        }
    }
    if(ans != -1)cout << "Escape possible in " << ans << " steps.\n";
    else cout << "The poor student is trapped!\n";
    return 0;
}