#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++) #define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--) #define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--) #define DRI(a) int a; scanf("%d ", &a); #define DRII(a, b) int a, b; scanf("%d %d ", &a, &b); //#define RI(a) scanf("%d ", &a); #define RII(a, b) scanf("%d %d ", &a, &b); #define PB push_back #define MP make_pair #define ll long long #define ull unsigned long long #define MM(co, cim) memset((co), (cim), sizeof((co))) #define DEB(x) cerr << ">>> " << #x << " : " << x << endl; struct state { int r,c,p,d; }; #define UP 0 #define RI 1 #define DO 2 #define LE 3 int W, H, L; char ins[17]; char mp[107][107]; bool visited[107][107][13][5]; bool isEmpty(state s) { if(mp[s.r][s.c] == 'X') return false; return true; } bool isVisited(state s) { return (visited[s.r][s.c][s.p][s.d]); } void visit(state s) { visited[s.r][s.c][s.p][s.d] = true; } void BFS(int r, int c, int p, int d) { //cout << "bfs" << endl; queue q; state s; s.r = r; s.c = c; s.p = p; s.d = d; if(isVisited(s)) return; q.push(s); while(!q.empty()) { s = q.front(); q.pop(); if(!isEmpty(s)) continue; if(isVisited(s)) continue; visit(s); if(ins[s.p] == 'S') { s.p = (s.p-1+L)%L; switch(s.d) { case UP: s.r++; break; case DO: s.r--; break; case LE: s.c++; break; case RI: s.c--; break; } // test wall bool stay = false; if(!isEmpty(s)) stay = true; switch(s.d) { case UP: s.r--; break; case DO: s.r++; break; case LE: s.c--; break; case RI: s.c++; break; } if(stay) q.push(s); switch(s.d) { case UP: s.r--; break; case DO: s.r++; break; case LE: s.c--; break; case RI: s.c++; break; } q.push(s); } else if(ins[s.p] == 'L') { s.p = (s.p-1+L)%L; s.d = (s.d+1+4)%4; q.push(s); } else if(ins[s.p] == 'R') { s.p = (s.p-1+L)%L; s.d = (s.d-1+4)%4; q.push(s); } } } int main () { while(cin >> H >> W) { FOR(i,0,H+3) FOR(j,0,W+3) mp[i][j] = 'X'; FOR(i,0,H) { cin >> &(mp[i+1][1]); } // TODO zarážky FOR(i,0,H+3) mp[i][0] = mp[i][W+1] = 'X'; FOR(i,0,W+3) mp[0][i] = mp[H+1][i] = 'X'; MM(visited, false); cin >> L; cin >> ins; FOR(i,1,H+1) { FOR(j,1,W+1) { if(mp[i][j] == 'E') { FOR(k,0,L) { FOR(d,0,4) { BFS(i,j,k,d); } } break; } } } bool poss = true; int cnt = 0; FOR(i,1,H+1) { FOR(j,1,W+1) { bool v = false; FOR(p,0,L) { if(visited[i][j][p][2]) v = true; } if(v) cnt++; else if(mp[i][j] != 'X') poss = false; } } if(poss) cout << "OK" << endl; else cout << cnt << endl; } return 0; }