#include #include #include #include #include #include #include #include #include #define FOR(i, v) for (int i = 0; i < v; i++) #define FORD(i, v) for (int i = v - 1; i >= 0; i--) #define REP(i, v, x) for (int i = v; i <= x; i++) #define REPD(i, v, x) for (int i = v; i >= x; i--) #define pb push_back #define fi first #define se second #define mp make_pair #define MAXB 1000 using namespace std; typedef long long i64; typedef unsigned long long u64; char buf[MAXB]; //fgets(buf, MAXB, stdin); void read(int n, char *s, ...) { int p = 0, v; va_list par; va_start(par, s); while (n--) { while (s[p] == ' ') p++; v = 0; while (isdigit(s[p])) v = v * 10 + s[p++] - '0'; *(va_arg(par, int*)) = v; } va_end(par); } int n, m; char b[110][110]; int sx, sy; int keys[256]; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, 1, -1}; struct state { int x, y, k, d; }; queue q; bool vis[110][110][16]; int bfs() { state t, t2; char c; t.x = sx; t.y = sy; t.d = 0; t.k = 0; while (!q.empty()) q.pop(); q.push(t); vis[t.x][t.y][t.k] = true; while (!q.empty()) { t = q.front(); q.pop(); t2.d = t.d + 1; FOR(i, 4) { t2.x = t.x + dx[i]; t2.y = t.y + dy[i]; t2.k = t.k; if (t2.x < 0 || t2.y < 0 || t2.x >= n || t2.y >= m) continue; c = b[t2.x][t2.y]; if (c == '#') continue; if (c == 'X') return t2.d; if (isupper(c) && !(t2.k & -keys[c])) continue; if (islower(c)) t2.k |= keys[c]; if (!vis[t2.x][t2.y][t2.k]) { q.push(t2); vis[t2.x][t2.y][t2.k] = true; } } } return -1; } int main() { memset(keys, 0, sizeof(keys)); keys['b'] = 1; keys['y'] = 2; keys['r'] = 4; keys['g'] = 8; keys['B'] = -1; keys['Y'] = -2; keys['R'] = -4; keys['G'] = -8; while (1) { scanf("%d %d", &n, &m); if (!n && !m) break; memset(vis, false, sizeof(vis)); FOR(i, n) { scanf("%s", b[i]); FOR(j, m) if (b[i][j] == '*') { b[i][j] = '.'; sx = i; sy = j; } } int res; if ((res = bfs()) == -1) printf("The poor student is trapped!\n"); else printf("Escape possible in %d steps.\n", res); } return 0; }