#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; bool operator==(const state& a) const { if(r == a.r && c == a.c && p == a.p && d == a.d) return true; return false; } }; #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]; vector prev[107][107][13][5]; bool isEmpty(state s) { if(mp[s.r][s.c] == 'X') return false; return true; } bool isVisited(state s, state sOld) { // all bool has = false; FOR(i,0,prev[s.r][s.c][s.p][s.d].size()) { if(prev[s.r][s.c][s.p][s.d][i] == sOld) { has = true; break; } } if(!has) prev[s.r][s.c][s.p][s.d].PB(sOld); if(visited[s.r][s.c][s.p][s.d]) return true; visited[s.r][s.c][s.p][s.d] = true; return false; //return (visited[s.r][s.c][s.p][s.d]); } bool isVisitedDummy(state s) { // all 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; 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') { state sOld = s; s.p = (s.p+1)%L; s.d = (s.d-1+4)%4; if(isVisited(s)) continue; q.push(s); } else if(ins[s.p] == 'R') { s.p = (s.p+1)%L; s.d = (s.d+1+4)%4; q.push(s); } } } */ void go(int r, int c) { int p, d; d = 0; p = 0; state s; state sOld; s.r = r; s.c = c; s.p = p; s.d = d; visit(s); while(true) { sOld = s; // step if(ins[s.p] == 'S') { switch(s.d) { case UP: s.r--; break; case DO: s.r++; break; case LE: s.c--; break; case RI: s.c++; break; } if(!isEmpty(s)) { switch(s.d) { case UP: s.r++; break; case DO: s.r--; break; case LE: s.c++; break; case RI: s.c--; break; } } } else if(ins[s.p] == 'L') { s.d = (s.d-1+4)%4; } else if(ins[s.p] == 'R') { s.d = (s.d+1+4)%4; } s.p = (s.p+1)%L; if(isVisited(s,sOld)) break; //+push } } int cnt; int BFSback(int r, int c, int p, int d) { state s; queue q; s.r = r; s.c = c; s.p = p; s.d = d; q.push(s); while(!q.empty()) { s = q.front(); q.pop(); if(isVisitedDummy(s)) continue; visit(s); if(s.d == UP && mp[s.r][s.c] != 'X' && s.p == 0) cnt++; FOR(i,0,prev[s.r][s.c][s.p][s.d].size()) { q.push(prev[s.r][s.c][s.p][s.d][i]); } } return cnt; } 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]); } 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) { FOR(k,0,L) { FOR(d,0,4) { prev[i][j][k][d].clear(); } } } } FOR(i,1,H+1) { FOR(j,1,W+1) { go(i,j); } } int total = 0; cnt = 0; FOR(i,1,H+1) { FOR(j,1,W+1) { if(mp[i][j] != 'X') { total++; } if(mp[i][j] == 'E') { MM(visited, false); FOR(k,0,L) { FOR(d,0,4) { BFSback(i,j,k,d); } } } } } if(cnt == total) cout << "OK" << endl; else cout << cnt << endl; /* bool poss = true; int cnt = 0; FOR(i,1,H+1) { FOR(j,1,W+1) { //cout << i << " " << j << endl; 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; }