#include #include using namespace std; char mapa[110][110]; int used[110][110][20]; int x, y; const int BLUE = 1; const int GREEN = 2; const int YELLOW = 4; const int RED = 8; struct sit { int x, y; int czas; int klucze; sit( int a = 0, int b = 0, int c = 0, int d = 0 ) : x(a), y(b), czas(c), klucze(d) {} }; inline int czy_moge( int X, int Y, int klucze ) { if ( X < 0 or X >= x or Y < 0 or Y >= y ) return -1; if ( used[X][Y][klucze] == 1 ) return -1; if ( mapa[X][Y] == '.' ) return 0; if ( mapa[X][Y] == '#' ) return -1; if ( mapa[X][Y] == '*' ) return 0; if ( mapa[X][Y] == 'X' ) return -2; char m = mapa[X][Y]; if ( m == 'b' ) return BLUE; if ( m == 'r' ) return RED; if ( m == 'y' ) return YELLOW; if ( m == 'g' ) return GREEN; if ( m == 'B' and klucze & BLUE ) return 0; if ( m == 'G' and klucze & GREEN ) return 0; if ( m == 'R' and klucze & RED ) return 0; if ( m == 'Y' and klucze & YELLOW ) return 0; return -1; } int fun() { int startx, starty; scanf("%d %d", &x, &y); if ( x == 0 and y == 0 ) return 1; for ( int i = 0; i <= x; i++ ) for ( int j = 0; j <= y; j++ ) for ( int k = 0; k < 20; k++ ) used[i][j][k] = 0; for ( int i = 0; i < x; i++ ) { for ( int j = 0; j < y; j++ ) { scanf(" %c", &mapa[i][j]); if ( mapa[i][j] == '*' ) { startx = i; starty = j; } } } deque< sit > Q; Q.push_back( sit(startx, starty, 0) ); while ( Q.size() > 0 ) { sit A = Q.front(); Q.pop_front(); int nx, ny, w; // do gory nx = A.x; ny = A.y - 1; w = czy_moge(nx, ny, A.klucze); if ( w == -2 ) { printf("Escape possible in %d steps.\n", A.czas + 1); return 0; } else if ( w == -1 ) { } else { Q.push_back( sit(nx, ny, A.czas+1, A.klucze|w) ); used[nx][ny][A.klucze|w] = 1; } // w dol nx = A.x; ny = A.y + 1; w = czy_moge(nx, ny, A.klucze); if ( w == -2 ) { printf("Escape possible in %d steps.\n", A.czas + 1); return 0; } else if ( w == -1 ) { } else { Q.push_back( sit(nx, ny, A.czas+1, A.klucze|w) ); used[nx][ny][A.klucze|w] = 1; } // w prawo nx = A.x + 1; ny = A.y; w = czy_moge(nx, ny, A.klucze); if ( w == -2 ) { printf("Escape possible in %d steps.\n", A.czas + 1); return 0; } else if ( w == -1 ) { } else { Q.push_back( sit(nx, ny, A.czas+1, A.klucze|w) ); used[nx][ny][A.klucze|w] = 1; } // w lewo nx = A.x - 1; ny = A.y; w = czy_moge(nx, ny, A.klucze); if ( w == -2 ) { printf("Escape possible in %d steps.\n", A.czas + 1); return 0; } else if ( w == -1 ) { } else { Q.push_back( sit(nx, ny, A.czas+1, A.klucze|w) ); used[nx][ny][A.klucze|w] = 1; } } printf("The poor student is trapped!\n"); return 0; } int main() { while ( ! fun() ) ; return 0; }