Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstring>
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <map>
- #include <stack>
- #include <set>
- using namespace std;
- const int maxn = 105;
- int n, m, sz;
- char mat[maxn][maxn];
- int dp[maxn][maxn][maxn];
- string s;
- int di[] = {-1, 1, 0, 0};
- int dj[] = {0, 0, -1, 1};
- set<pair<int, int> > st;
- int rec(int i, int j, int at) {
- if(at == sz) {
- st.insert({i, j});
- // cout << "DA" << endl;
- return 1;
- }
- if(dp[i][j][at] != -1) {
- return dp[i][j][at];
- }
- int result = 0;
- if(s[at] == 'N') {
- if(i - 1 >= 0 and mat[i - 1][j] != '#') {
- result = max(result, rec(i - 1, j, at + 1));
- }
- }
- if(s[at] == 'S') {
- if(i + 1 < n and mat[i + 1][j] != '#') {
- result = max(result, rec(i + 1, j, at + 1));
- }
- }
- if(s[at] == 'W') {
- if(j - 1 >= 0 and mat[i][j - 1] != '#') {
- result = max(result, rec(i, j - 1, at + 1));
- }
- }
- if(s[at] == 'E') {
- if(j + 1 < m and mat[i][j + 1] != '#') {
- result = max(result, rec(i, j + 1, at + 1));
- }
- }
- if(s[at] == '?') {
- for(int k = 0; k < 4; k++) {
- int ti = i + di[k];
- int tj = j + dj[k];
- if(ti >= 0 and tj >= 0 and ti < n and tj < m and mat[ti][tj] != '#') {
- result = max(result, rec(ti, tj, at + 1));
- }
- }
- }
- return dp[i][j][at] = result;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin >> n >> m >> sz;
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < m; j++) {
- cin >> mat[i][j];
- }
- }
- cin >> s;
- int res = 0;
- memset(dp, -1, sizeof dp);
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < m; j++) {
- if(mat[i][j] != '#') {
- // res++;
- }
- if(mat[i][j] != '#' and rec(i, j, 0) == 1) {
- }
- }
- }
- cout << st.size() << endl;
- return 0;
- }
- /*
- 5 9 7
- ...##....
- ..#.##..#
- ..#....##
- .##...#..
- ....#....
- WS?EE??
- **/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement