#include "bits/stdc++.h" using namespace std; const int MAXN = 505; const int MAXM = 5005; int r,c,m; string direction; int dir[MAXM]; bool arr[MAXN][MAXN]; queue<tuple<int,int,bool>> q; unordered_set<string> s; int xD[4] = {-1,0,1,0}; int yD[4] = {0,1,0,-1}; int main() { #ifdef LOCAL freopen("submission/input.in", "r", stdin); freopen("submission/output.out", "w", stdout); #else ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #endif cin >> r >> c >> m; for (int i = 1; i<=r; i++) { string s; cin >> s; for (int j = 1; j<=c; j++) { if (s[j-1] == '.') { arr[i][j] = true; q.push({i,j,false}); } } } cin >> direction; for (int i = 0; i<m; i++) { if (direction[i] == 'N') dir[i] = 0; if (direction[i] == 'E') dir[i] = 1; if (direction[i] == 'S') dir[i] = 2; if (direction[i] == 'W') dir[i] = 3; if (direction[i] == '?') dir[i] = -1; } int dist = 0; bool done = false; while (dist!=m) { int x = get<0>(q.front()), y = get<1>(q.front()); bool _new = get<2>(q.front()); q.pop(); if (_new) { s.clear(); dist++; done = false; if (dist == m) break; } if (dir[dist] == -1) { for (int i = 0; i<4; i++) { int curx = x+xD[i], cury = y+yD[i]; if (!arr[curx][cury] || s.count(to_string(curx)+' '+to_string(cury))!=0) continue; s.insert(to_string(curx)+' '+to_string(cury)); q.push({curx,cury,!done}); if (!done) done = true; } continue; } int curx = x+xD[dir[dist]], cury = y+yD[dir[dist]]; if (!arr[curx][cury] || s.count(to_string(curx)+' '+to_string(cury))!=0) continue; s.insert(to_string(curx)+' '+to_string(cury)); q.push({curx,cury,!done}); if (!done) done = true; } cout << q.size()+1 << '\n'; return 0; }