#include #include #include using namespace std; char lab[110][110]; int dist[110][110][2][2][2][2]; typedef int coord; typedef struct point_t { coord x, y; coord k1, k2, k3, k4; }; int xi, yi; coord x, y; point_t startpoint; const int inf = 0x66666666; const char charinf = 0x66; queue pq; point_t aktpoint; point_t newpoint; int aktdist; int *newdist_ptr; int megoldas; bool mehetek; int main() { coord i, j; char c; while (scanf("%d %d ", &yi, &xi) && xi) { x = xi; y = yi; for (i = 0; i <= x + 1; ++i) { lab[i][0] = '#'; lab[i][y+1] = '#'; } for (j = 0; j <= y + 1; ++j) { lab[0][j] = '#'; lab[x+1][j] = '#'; } for (j = 1; j <= y; ++j) { for (i = 1; i <= x; ++i) { scanf("%c", &c); lab[i][j] = c; if (c == '*') { startpoint.x = i; startpoint.y = j; startpoint.k1 = 0; startpoint.k2 = 0; startpoint.k3 = 0; startpoint.k4 = 0; } } scanf(" "); } memset(dist, charinf, sizeof(dist)); dist[startpoint.x][startpoint.y][startpoint.k1][startpoint.k2][startpoint.k3][startpoint.k4] = 0; //pq.clear(); while (!pq.empty()) pq.pop(); pq.push(startpoint); megoldas = 0; while (!pq.empty()) { aktpoint = pq.front(); pq.pop(); aktdist = dist[aktpoint.x][aktpoint.y][aktpoint.k1][aktpoint.k2][aktpoint.k3][aktpoint.k4]; newpoint = aktpoint; --newpoint.x; if (lab[newpoint.x][newpoint.y] == 'b') newpoint.k1 = 1; if (lab[newpoint.x][newpoint.y] == 'y') newpoint.k2 = 1; if (lab[newpoint.x][newpoint.y] == 'r') newpoint.k3 = 1; if (lab[newpoint.x][newpoint.y] == 'g') newpoint.k4 = 1; newdist_ptr = &dist[newpoint.x][newpoint.y][newpoint.k1][newpoint.k2][newpoint.k3][newpoint.k4]; if (lab[newpoint.x][newpoint.y] == 'X') { megoldas = aktdist + 1; break; } mehetek = lab[newpoint.x][newpoint.y] != '#'; if (lab[newpoint.x][newpoint.y] == 'B' && !newpoint.k1) mehetek = false; if (lab[newpoint.x][newpoint.y] == 'Y' && !newpoint.k2) mehetek = false; if (lab[newpoint.x][newpoint.y] == 'R' && !newpoint.k3) mehetek = false; if (lab[newpoint.x][newpoint.y] == 'G' && !newpoint.k4) mehetek = false; if (mehetek && *newdist_ptr > aktdist + 1) { *newdist_ptr = aktdist + 1; pq.push(newpoint); } newpoint = aktpoint; ++newpoint.x; if (lab[newpoint.x][newpoint.y] == 'b') newpoint.k1 = 1; if (lab[newpoint.x][newpoint.y] == 'y') newpoint.k2 = 1; if (lab[newpoint.x][newpoint.y] == 'r') newpoint.k3 = 1; if (lab[newpoint.x][newpoint.y] == 'g') newpoint.k4 = 1; newdist_ptr = &dist[newpoint.x][newpoint.y][newpoint.k1][newpoint.k2][newpoint.k3][newpoint.k4]; if (lab[newpoint.x][newpoint.y] == 'X') { megoldas = aktdist + 1; break; } mehetek = lab[newpoint.x][newpoint.y] != '#'; if (lab[newpoint.x][newpoint.y] == 'B' && !newpoint.k1) mehetek = false; if (lab[newpoint.x][newpoint.y] == 'Y' && !newpoint.k2) mehetek = false; if (lab[newpoint.x][newpoint.y] == 'R' && !newpoint.k3) mehetek = false; if (lab[newpoint.x][newpoint.y] == 'G' && !newpoint.k4) mehetek = false; if (mehetek && *newdist_ptr > aktdist + 1) { *newdist_ptr = aktdist + 1; pq.push(newpoint); } newpoint = aktpoint; --newpoint.y; if (lab[newpoint.x][newpoint.y] == 'b') newpoint.k1 = 1; if (lab[newpoint.x][newpoint.y] == 'y') newpoint.k2 = 1; if (lab[newpoint.x][newpoint.y] == 'r') newpoint.k3 = 1; if (lab[newpoint.x][newpoint.y] == 'g') newpoint.k4 = 1; newdist_ptr = &dist[newpoint.x][newpoint.y][newpoint.k1][newpoint.k2][newpoint.k3][newpoint.k4]; if (lab[newpoint.x][newpoint.y] == 'X') { megoldas = aktdist + 1; break; } mehetek = lab[newpoint.x][newpoint.y] != '#'; if (lab[newpoint.x][newpoint.y] == 'B' && !newpoint.k1) mehetek = false; if (lab[newpoint.x][newpoint.y] == 'Y' && !newpoint.k2) mehetek = false; if (lab[newpoint.x][newpoint.y] == 'R' && !newpoint.k3) mehetek = false; if (lab[newpoint.x][newpoint.y] == 'G' && !newpoint.k4) mehetek = false; if (mehetek && *newdist_ptr > aktdist + 1) { *newdist_ptr = aktdist + 1; pq.push(newpoint); } newpoint = aktpoint; ++newpoint.y; if (lab[newpoint.x][newpoint.y] == 'b') newpoint.k1 = 1; if (lab[newpoint.x][newpoint.y] == 'y') newpoint.k2 = 1; if (lab[newpoint.x][newpoint.y] == 'r') newpoint.k3 = 1; if (lab[newpoint.x][newpoint.y] == 'g') newpoint.k4 = 1; newdist_ptr = &dist[newpoint.x][newpoint.y][newpoint.k1][newpoint.k2][newpoint.k3][newpoint.k4]; if (lab[newpoint.x][newpoint.y] == 'X') { megoldas = aktdist + 1; break; } mehetek = lab[newpoint.x][newpoint.y] != '#'; if (lab[newpoint.x][newpoint.y] == 'B' && !newpoint.k1) mehetek = false; if (lab[newpoint.x][newpoint.y] == 'Y' && !newpoint.k2) mehetek = false; if (lab[newpoint.x][newpoint.y] == 'R' && !newpoint.k3) mehetek = false; if (lab[newpoint.x][newpoint.y] == 'G' && !newpoint.k4) mehetek = false; if (mehetek && *newdist_ptr > aktdist + 1) { *newdist_ptr = aktdist + 1; pq.push(newpoint); } } if (megoldas) { printf("Escape possible in %d steps.\n", megoldas); } else { printf("The poor student is trapped!\n"); } } return 0; }