#include #include #include #include #include #define WALL 'X' #define EMPTY '.' #define FINISH 'E' #define UNKNOWN 0 #define SUCCESS 1 #define FAILURE 2 #define LEFT 0 #define RIGHT 1 #define UP 2 #define DOWN 3 using namespace std; char maze[102][102]; int states[102][102][10][4]; char commands[10]; int poziceVeFronte = 0; struct state { int x; int y; int cmdIndex; int rotation; state(int _x, int _y, int _cmdIndex, int _rotation) { x= _x; y = _y; cmdIndex = _cmdIndex; rotation = _rotation; } state() { } }; state fronta[101*101*10*4]; int exitX; int exitY; int RotateLeft(int oldrotation) { switch(oldrotation) { case LEFT: return DOWN; case DOWN: return RIGHT; case RIGHT: return UP; case UP: return LEFT; } return -1; } int RotateRight(int oldrotation) { switch(oldrotation) { case LEFT: return UP; case DOWN: return LEFT; case RIGHT: return DOWN; case UP: return RIGHT; } return -1; } int aheadX(int x, int rotation) { switch(rotation) { case LEFT: return x-1; case DOWN: return x; case RIGHT: return x+1; case UP: return x; } return -1; } int aheadY(int y, int rotation) { switch(rotation) { case LEFT: return y; case DOWN: return y+1; case RIGHT: return y; case UP: return y-1; } return -1; } int main() { int W, H, CommandLength; while (scanf("%d %d", &H, &W) == 2) { // Read maze scanf("\n"); for (int y = 1; y <= H; y++) { for (int x = 1; x <= W; x++) { scanf("%c", &maze[x][y]); if (maze[x][y] == 'E') { exitX = x; exitY = y; } } scanf("\n"); } for (int x = 0; x <= W; x++) { maze[x][0] = WALL; maze[x][H+1] = WALL; } for (int y = 0; y <= H; y++) { maze[0][y] = WALL; maze[W+1][y] = WALL; } scanf("%d\n", &CommandLength); for (int i = 0; i < CommandLength; i++) { scanf("%c", &commands[i]); } // Empty states for (int y = 1; y <= H; y++) { for (int x = 1; x <= W; x++) { if (x == exitX && y == exitY) { for (int ppos = 0; ppos < CommandLength; ppos++) { for (int state = 0; state < 4; state++) { states[x][y][ppos][state] = SUCCESS; } } } else { for (int ppos = 0; ppos < CommandLength; ppos++) { for (int state = 0; state < 4; state++) { states[x][y][ppos][state] = UNKNOWN; } } } } } // Traverse the maze bool allSuccess = true; int successCount = 0; for (int x = 1; x <= W; x++) { for (int y = 1; y <= H; y++) { if (maze[x][y] == WALL) { continue; } int cmdIndex = 0; int posx = x; int newx; int posy = y; int newy; poziceVeFronte = -1; int rotation = UP; while (states[posx][posy][cmdIndex][rotation] == UNKNOWN) { poziceVeFronte++; fronta[poziceVeFronte] = state(posx, posy, cmdIndex, rotation); states[posx][posy][cmdIndex][rotation] = FAILURE; switch(commands[cmdIndex]) { case 'S': newx = aheadX(posx, rotation); newy = aheadY(posy, rotation); if (maze[newx][newy] != WALL) { posx = newx; posy = newy; } break; case 'L': rotation = RotateLeft(rotation); break; case 'R': rotation = RotateRight(rotation); break; } cmdIndex++; if (cmdIndex == CommandLength) cmdIndex = 0; } if (states[posx][posy][cmdIndex][rotation] == SUCCESS) { successCount++; for (int i = poziceVeFronte; i >= 0; i--) { states[fronta[i].x][fronta[i].y][fronta[i].cmdIndex][fronta[i].rotation] = SUCCESS; } } else { allSuccess = false; } } } // Count result if (allSuccess) { printf("OK\n"); } else { printf("%d\n", successCount); } } }