fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define FOR(i, l, r) for(int i = (l); i <= (r); i++)
  6. #define FOD(i, r, l) for(int i = (r); i >= (l); i--)
  7. #define fi first
  8. #define se second
  9. const int maxn = 1e3 + 10;
  10. const int mod  = 1e9 + 7;
  11.  
  12. int dx[] = {0, 0, 1, -1};
  13. int dy[] = {1, -1, 0, 0};
  14.  
  15. int n, m;
  16. char a[maxn][maxn];
  17. int v[maxn * maxn]; 
  18. int sx, sy;
  19. queue<pair<int, int>> q;
  20. bool vis[maxn * maxn];
  21. int par[maxn * maxn];
  22. vector<int> p;
  23. int dp[maxn * maxn];
  24.  
  25. bool check(int x, int y)
  26. {
  27.     return x >= 0 && x < n && y >= 0 && y < m;
  28. }
  29. signed main()
  30. {
  31.     ios_base::sync_with_stdio(0);
  32.     cin.tie(0);cout.tie(0);
  33.  
  34.     cin >> n >> m;
  35.     FOR(i, 0, n - 1) FOR(j, 0, m - 1) cin >> a[i][j];
  36.     FOR(i, 0, n - 1) FOR(j, 0, m - 1)
  37.     {
  38.         int x;
  39.         cin >> x;
  40.         v[i * m + j] = x;
  41.         if (a[i][j] == 'O') sx = i, sy = j;
  42.     }
  43.  
  44.     int rt = sx * m + sy;
  45.     memset(par, -1, sizeof par);
  46.     p.push_back(rt);
  47.     q.push({sx, sy});
  48.     vis[rt] = true;
  49.     while (!q.empty())
  50.     {
  51.         auto [x, y] = q.front();
  52.         q.pop();
  53.         for (int k = 0; k < 4; k++) 
  54.         {
  55.             int ux = x + dx[k];
  56.             int uy = y + dy[k];
  57.             int vx = ux + dx[k];
  58.             int vy = uy + dy[k];
  59.             if (!check(ux, uy) || !check(vx, vy)) continue;
  60.             bool flag = false;
  61.             if (dx[k] ==  1 && dy[k] ==  0) flag = (a[ux][uy]=='V' && a[vx][vy]=='.');
  62.             if (dx[k] == -1 && dy[k] ==  0) flag = (a[ux][uy]=='.' && a[vx][vy]=='V');
  63.             if (dx[k] ==  0 && dy[k] ==  1) flag = (a[ux][uy]=='H' && a[vx][vy]=='.');
  64.             if (dx[k] ==  0 && dy[k] == -1) flag = (a[ux][uy]=='.' && a[vx][vy]=='H');
  65.             if (!flag) continue;
  66.             int nx = vx * m + vy;
  67.             if (!vis[nx])
  68.             {
  69.                 vis[nx] = true;
  70.                 par[nx] = x * m + y;
  71.                 p.push_back(nx);
  72.                 q.push({vx, vy});
  73.             }
  74.         }
  75.     }
  76.  
  77.     for (int i = p.size() - 1; i >= 0; i--)
  78.     {
  79.         int u = p[i];
  80.         dp[u] += v[u];
  81.         int p = par[u];
  82.         if (p != -1 && dp[u] > 0) dp[p] += dp[u];
  83.     }
  84.     cout << dp[rt] << "\n";
  85. }
Success #stdin #stdout 0.01s 13844KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/CmqGMu
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!