#include #include using namespace std; class ccheck { public: int rule; int angle; ccheck(int prule, int pangle) : rule(prule), angle(pangle) {} }; class square { public: char type; int angle; int rule; vector rules; bool addRule(ccheck rule) { for(unsigned int i = 0; i < rules.size(); i++) { if(rules[i].rule == rule.rule && rules[i].angle == rule.angle) return false; } rules.push_back(rule); return true; } }; bool exists(int height, int width, int x, int y) { if(x < 0 || x >= height || y < 0 || y >= width) return false; return true; } bool check(square** data, int height, int width, int x, int y, char* rules, int numrules) { for(int i = 0; i < height; i++) { for(int j = 0; j < width; j++) { data[i][j].angle = -1; data[i][j].rule = -1; data[i][j].rules.clear(); } } //top . 0 int currule = 0; int angle = 0; while(true) { char rule = rules[currule]; if(!data[x][y].addRule(ccheck(currule, angle))) return false; //cout << "rule: " << rule << ", angle: " << angle << endl; if(rule == 'L') { angle -= 1; if(angle < 0) angle = 3; } else if(rule == 'R') { angle += 1; angle %= 4; } else { //step int newx = x, newy = y; if(angle == 0) { if(exists(height, width, x - 1, y)) { newx = x - 1; } } else if(angle == 1) { if(exists(height, width, x, y + 1)) { newy = y + 1; } } else if(angle == 2) { if(exists(height, width, x+1, y)) { newx = x + 1; } } else { if(exists(height, width,x, y - 1)) { newy = y - 1; } } if(data[newx][newy].type == '.') { x = newx; y = newy; //cout << x << " " << y << endl; //data[x][y].angle = angle; //data[x][y].rule = currule; } else if(data[newx][newy].type == 'E') { //cout << "found" << endl; return true; } } currule++; currule %= numrules; } return true; } int main() { int height, width; while(cin >> height >> width) { int exits = 0; int freeTotal = 0; square** data = new square*[height]; for(int x = 0; x < height; x++) { data[x] = new square[width]; for(int y = 0; y < width; y++) { char dummy; cin >> dummy; data[x][y].type = dummy; data[x][y].angle = -1; if(dummy == '.') { freeTotal++; } else if(dummy == 'E') { exits++; } } } int numrules; cin >> numrules; char* rules = new char[numrules]; for(int x = 0; x < numrules; x++) { cin >> rules[x]; } int found = 0; bool ok = false; for(int i = 0; i < numrules; i++) { if(rules[i] == 'S') ok = true; } if(!ok) { cout << exits << endl; return 0; } //check(data, height, width, 1, 3, rules, numrules); for(int x = 0; x < height; x++) { for(int y = 0; y < width; y++) { if(data[x][y].type == '.') { if(check(data, height, width, x, y, rules, numrules)) { found++; } } } } if(found == freeTotal) { cout << "OK" << endl; } else { cout << (found + exits) << endl; } } return 0; }