#include #include #include typedef unsigned int uint; struct Bits { static const int EMPTY = -1, GOOD = -2, BAD = -3; int storage[4 * 10 * 100 * 100]; Bits() { memset(storage, 0xFF, sizeof(storage)); } int root(const int i) { if (storage[i] == EMPTY) return i; if (storage[i] < 0) return storage[i]; if (storage[i] == i) return i; const int result = root(storage[i]); connect(i, result); return result; } void connect(const int i, const int root) { storage[i] = root; } }; int main() { const uint UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3; char field[100 + 1][100 + 1]; char program[10 + 1]; while (true) { uint h, w; std::cin >> h >> w; if (std::cin.fail()) return 0; for (uint i = 0; i < h; ++i) std::cin >> field[i]; uint proglen; std::cin >> proglen >> program; Bits bits; uint successful = 0; uint all = 0; for (uint sr = 0; sr < h; ++sr) for (uint sc = 0; sc < w; ++sc) if (field[sr][sc] != 'X') { uint r = sr; uint c = sc; uint steps = 0; uint ip = 0; uint dir = UP; const int start = dir + 4 * (ip + proglen * (r + h * (c))); while (true) { // std::cout << "here: " << r << "x" << c << std::endl; const int state = dir + 4 * (ip + proglen * (r + h * (c))); if (field[r][c] == 'E' || bits.root(state) == Bits::GOOD) { // std::cout << "yay: " << sr << "x" << sc << std::endl; successful++; bits.connect(start, Bits::GOOD); break; } if (state != start && bits.root(state) == start || bits.root(state) == Bits::BAD) { // std::cout << "boo: " << sr << "x" << sc << std::endl; bits.connect(start, Bits::BAD); break; } if (steps == w * h * 4 * proglen) break; bits.connect(state, start); switch (program[steps % proglen]) { case 'S': switch (dir) { case UP: if (r > 0 && field[r - 1][c] != 'X') r--; break; case RIGHT: if (c + 1 < w && field[r][c + 1] != 'X') c++; break; case DOWN: if (r + 1 < h && field[r + 1][c] != 'X') r++; break; case LEFT: if (c > 0 && field[r][c - 1] != 'X') c--; break; } break; case 'L': dir--; dir %= 4; break; case 'R': dir++; dir %= 4; break; } steps++; ip++; ip %= proglen; } all++; } if (successful == all) std::cout << "OK"; else std::cout << successful; std::cout << std::endl; } }