rembocoder

Untitled

Apr 27th, 2023
851
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.24 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int int64_t
  6.  
  7. int dx[4] = {2, -2, 0, 0}, dy[4] = {0, 0, 2, -2};
  8. string endpoint = "V^><";
  9.  
  10. vector<string> s;
  11. int dp[500][500];
  12. int a[500][500];
  13. bool used[500][500];
  14. int n, m;
  15.  
  16. bool ok(int x, int y) {
  17.     return 0 <= x && x < n && 0 <= y && y < m;
  18. }
  19.  
  20. void dfs(int x, int y) {
  21.     used[x][y] = true;
  22.     dp[x][y] = a[x][y];
  23.     for (int dir = 0; dir < 4; dir++) {
  24.         int to_x = x + dx[dir];
  25.         int to_y = y + dy[dir];
  26.         if (ok(to_x, to_y) && !used[to_x][to_y] && s[to_x][to_y] == endpoint[dir]) {
  27.             dfs(to_x, to_y);
  28.             dp[x][y] += max(0ll, dp[to_x][to_y]);
  29.         }
  30.     }
  31. }
  32.  
  33. int32_t main() {
  34.     ios_base::sync_with_stdio(false);
  35.     cin.tie(0); cout.tie(0);
  36.     cin >> n >> m;
  37.     s.resize(n);
  38.     for (int i = 0; i < n; i++) {
  39.         cin >> s[i];
  40.     }
  41.     for (int i = 0; i < n; i++) {
  42.         for (int j = 0; j < m; j++) {
  43.             cin >> a[i][j];
  44.         }
  45.     }
  46.     int sx = -1, sy = -1;
  47.     for (int i = 0; i < n; i++) {
  48.         for (int j = 0; j < m; j++) {
  49.             if (s[i][j] == '.') {
  50.                 sx = i;
  51.                 sy = j;
  52.             }
  53.         }
  54.     }
  55.     dfs(sx, sy);
  56.     cout << dp[sx][sy];
  57. }
  58.  
Advertisement
Add Comment
Please, Sign In to add comment