#include #include #include #define MAXN 200 #define MAXV (MAXN * MAXN * 4) char Maze[MAXN][MAXN]; char Ins[MAXN]; int h, w, l; int nEmpty; int Degree[MAXV]; int CurIndex[MAXV]; int Fol[MAXV]; int iFol[MAXV]; struct POS { int x; int y; int d; //d = -1 means exit reached }; struct EDGE { int From; int To; }; int n; int m; int Exit; EDGE Edge[MAXV]; int Q[MAXV]; int QBeg, QEnd; int Visited[MAXV]; int PosToInt(const POS& Pos) { if(Pos.d == -1) { return Exit; } return (Pos.x * h * 4) + (Pos.y * 4) + Pos.d; } POS IntToPos(int a) { if(a == h * w * 4) { return (POS) {0, 0, -1}; } return (POS) {a / (h * 4), (a / 4) % h, a % 4}; } void Move(POS& Pos, char ins) { if(Maze[Pos.x][Pos.y] == 'E') { Pos.d = -1; return; } if(Pos.d == -1) { return; } if(ins == 'R') { Pos.d = (Pos.d + 1) % 4; return; } if(ins == 'L') { Pos.d = (Pos.d + 3) % 4; return; } int xNew = Pos.x; int yNew = Pos.y; switch(Pos.d) { case 0: yNew--; break; case 1: xNew++; break; case 2: yNew++; break; case 3: xNew--; break; } if(Maze[xNew][yNew] != 'X') { Pos.x = xNew; Pos.y = yNew; } } void Run(POS& Pos) { for(int i = 0; i < l; i++) { Move(Pos, Ins[i]); } } int main() { while(scanf("%d%d", &h, &w) > 0) { nEmpty = 0; getchar(); for(int y = 1; y <= h; y++) { for(int x = 1; x <= w; x++) { if((Maze[x][y] = getchar()) != 'X') { nEmpty++; } } getchar(); } h += 2; w += 2; Exit = w * h * 4; n = Exit + 1; scanf("%d", &l); getchar(); for(int i = 0; i < l; i++) { Ins[i] = getchar(); } for(int x = 0; x < w; x++) { Maze[x][0] = 'X'; Maze[x][h - 1] = 'X'; } for(int y = 0; y < h; y++) { Maze[0][y] = 'X'; Maze[w - 1][y] = 'X'; } /*for(int y = 0; y < h; y++) { for(int x = 0; x < w; x++) { putchar(Maze[x][y]); } putchar('\n'); } for(int i = 0; i < l; i++) { putchar(Ins[i]); } putchar('\n');*/ m = 0; for(int x = 0; x < w; x++) { for(int y = 0; y < h; y++) { if(Maze[x][y] == 'X') { continue; } for(int d = 0; d < 4; d++) { POS OldPos = (POS) {x, y, d}; POS NewPos = OldPos; Run(NewPos); Edge[m++] = (EDGE) {PosToInt(NewPos), PosToInt(OldPos)}; } } } memset(Degree, 0, sizeof(Degree)); for(int i = 0; i < m; i++) { Degree[Edge[i].From]++; } iFol[0] = 0; for(int i = 0; i < n; i++) { iFol[i + 1] = iFol[i] + Degree[i]; CurIndex[i] = iFol[i]; } for(int i = 0; i < m; i++) { int f = Edge[i].From; int t = Edge[i].To; Fol[CurIndex[f]++] = t; } QBeg = 0; QEnd = 0; memset(Visited, 0, sizeof(Visited)); Q[QEnd++] = Exit; Visited[Exit] = 1; while(QBeg < QEnd) { int cur = Q[QBeg++]; for(int j = iFol[cur]; j < iFol[cur + 1]; j++) { int t = Fol[j]; if(!(Visited[t])) { Q[QEnd++] = t; Visited[t] = 1; } } } int nOK = 0; for(int x = 0; x < w; x++) { for(int y = 0; y < h; y++) { if(Maze[x][y] == 'X') { continue; } int i = PosToInt((POS) {x, y, 0}); if(Visited[i]) { nOK++; } } } if(nOK == nEmpty) { printf("OK\n"); } else { printf("%d\n", nOK); } } return 0; }