#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define FOR(i,a,b) for(int i=a; i<=b; i++) #define PB push_back #define fi first #define se second #define make_pair #define PII pair #define SIZE(s) (int)(s).size() #define INF 987654321 #define ll long long //---------- #define MAX 105 #define MAX_I 12 #define MAX_D 4 char M[MAX][MAX]; int Y, X; int K; char ins[MAX_I]; char S[MAX][MAX][MAX_I][MAX_D]; int diry[] = {1,0,-1,0}; int dirx[] = {0,1,0,-1}; bool ok(int y, int x){ return y >= 0 && y < Y && x >=0 && x < X; } typedef struct State { int y; int x; int ii; int dir; } STATE; STATE nState(int x, int y, int ii, int dir) { STATE t; t.x = x; t.y = y; t.ii = ii; t.dir = dir; return t; } vector< STATE > H; void setHistory(char val){ STATE ss; FOR(i,0,SIZE(H)-1){ ss = H[i]; S[ ss.y ][ ss.x ][ ss.ii ][ ss.dir ] = val; } } #define DEBUG 0 char visit[MAX][MAX][MAX_I][MAX_D]; bool simulate(int y, int x){ if (DEBUG) printf("Zacina na: %d %d\n", y, x); memset(visit, 0, sizeof(char) * MAX * MAX * MAX_I * MAX_D); //FOR(i,0,Y-1) FOR(j,0,X-1) FOR(k,0,K-1) FOR(d,0,3) // if (visit[i][j][k][d] != 0) printf("ZLE"); //1 = ok, 2 = zle int ii = 0; int dir = 2; H.clear(); while(true){ if (DEBUG) printf("Som na: %d x %d, inst: %d, smer: %d\n", y, x, ii, dir); if (S[y][x][ii][dir] != 0){ setHistory( S[y][x][ii][dir] ); if (S[y][x][ii][dir] == 1) return true; else return false; } if (M[y][x] == 'E'){ setHistory(1); return true; } if (visit[y][x][ii][dir] == 1){ setHistory(2); return false; } H.PB( nState(y,x,ii,dir) ); visit[y][x][ii][dir] = 1; if ( ins[ii] == 'S' ){ int nx = x + dirx[dir]; int ny = y + diry[dir]; if (ok(ny, nx) && M[ny][nx] != 'X'){ x = nx; y = ny; } else{ if (DEBUG){ printf("Pause:"); if (!ok(ny, nx)) printf("VON\n"); else printf("%c\n", M[ny][nx]); } } } else if (ins[ii] == 'L'){ dir = (dir + 1) % 4; } else if (ins[ii] == 'R'){ dir = (dir + 3) % 4; } ii = (ii + 1) % K; } } int solve(){ /* FOR(i,0,Y-1){ FOR(j,0,X-1) printf("%c ", M[i][j]); printf("\n"); } printf("%d %d\n", ey, ex); FOR(i,0,K-1) printf("%c", ins[i]); puts(""); */ memset(S, 0, sizeof(char) * MAX * MAX * MAX_I * MAX_D); int sum = 0; FOR(i,0,Y-1) FOR(j,0,X-1) if (M[i][j] == '.'){ if (S[i][j][2][0] == 0) sum+= simulate(i,j); else if (S[i][j][2][0] == 1) sum+= 1; } return sum; } int main(){ while(scanf("%d %d\n", &Y, &X) == 2){ int free = 0; FOR(i,0,Y-1){ FOR(j,0,X-1){ M[i][j] = getchar(); if (M[i][j] == '.') free++; } getchar(); } scanf("%d\n", &K); FOR(i,0,K-1) ins[i] = getchar(); int res = solve(); if (res == free) printf("OK\n"); else printf("%d\n", res); } return 0; }