Advertisement
Josif_tepe

Untitled

Apr 24th, 2023
687
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.13 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <map>
  7. #include <stack>
  8. #include <set>
  9. using namespace std;
  10. const int maxn = 105;
  11. int n, m, sz;
  12. char mat[maxn][maxn];
  13. int dp[maxn][maxn][maxn];
  14. string s;
  15. int di[] = {-1, 1, 0, 0};
  16. int dj[] = {0, 0, -1, 1};
  17. set<pair<int, int> > st;
  18. int rec(int i, int j, int at) {
  19.     if(at == sz) {
  20.         st.insert({i, j});
  21. //        cout << "DA" << endl;
  22.         return 1;
  23.     }
  24.     if(dp[i][j][at] != -1) {
  25.         return dp[i][j][at];
  26.     }
  27.     int result = 0;
  28.     if(s[at] == 'N') {
  29.         if(i - 1 >= 0 and mat[i - 1][j] != '#') {
  30.             result = max(result, rec(i - 1, j, at + 1));
  31.         }
  32.     }
  33.     if(s[at] == 'S') {
  34.         if(i + 1 < n and mat[i + 1][j] != '#') {
  35.             result = max(result, rec(i + 1, j, at + 1));
  36.         }
  37.     }
  38.     if(s[at] == 'W') {
  39.         if(j - 1 >= 0 and mat[i][j - 1] != '#') {
  40.             result = max(result, rec(i, j - 1, at + 1));
  41.         }
  42.     }
  43.     if(s[at] == 'E') {
  44.         if(j + 1 < m and mat[i][j + 1] != '#') {
  45.             result = max(result, rec(i, j + 1, at + 1));
  46.         }
  47.     }
  48.     if(s[at] == '?') {
  49.         for(int k = 0; k < 4; k++) {
  50.             int ti = i + di[k];
  51.             int tj = j + dj[k];
  52.             if(ti >= 0 and tj >= 0 and ti < n and tj < m and mat[ti][tj] != '#') {
  53.                 result = max(result, rec(ti, tj, at + 1));
  54.             }
  55.         }
  56.     }
  57.     return  dp[i][j][at] = result;
  58. }
  59. int main() {
  60.     ios_base::sync_with_stdio(false);
  61.     cin >> n >> m >> sz;
  62.     for(int i = 0; i < n; i++) {
  63.         for(int j = 0; j < m; j++) {
  64.             cin >> mat[i][j];
  65.         }
  66.     }
  67.     cin >> s;
  68.     int res = 0;
  69.     memset(dp, -1, sizeof dp);
  70.     for(int i = 0; i < n; i++) {
  71.         for(int j = 0; j < m; j++) {
  72.             if(mat[i][j] != '#') {
  73. //                res++;
  74.             }
  75.             if(mat[i][j] != '#' and rec(i, j, 0) == 1) {
  76.                
  77.             }
  78.         }
  79.     }
  80.     cout << st.size() << endl;
  81.     return 0;
  82. }
  83. /*
  84.  5 9 7
  85. ...##....
  86. ..#.##..#
  87. ..#....##
  88. .##...#..
  89. ....#....
  90. WS?EE??
  91.  
  92.  
  93.  **/
  94.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement