Advertisement
Guest User

Untitled

a guest
Apr 11th, 2020
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.68 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<int, int> pii;
  5.  
  6. int T, R, C;
  7. int dr[] = {0, 0, -1, 1};
  8. int dc[] = {-1, 1, 0, 0};
  9. vector<vector<int>> mat, dir[4];
  10. const int UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3;
  11.  
  12. int main() {
  13.   scanf("%d", &T);
  14.   for (int t = 1; t <= T; ++t) {
  15.     scanf("%d%d", &R, &C);
  16.     mat.assign(R, vector<int>(C));
  17.     for (int i = 0; i < 4; ++i) {
  18.       dir[i].assign(R, vector<int>(C));
  19.     }
  20.     for (int i = 0; i < R; ++i) {
  21.       for (int j = 0; j < C; ++j) {
  22.         scanf("%d", &mat[i][j]);
  23.         dir[UP][i][j] = i-1;
  24.         dir[DOWN][i][j] = i+1;
  25.         dir[LEFT][i][j] = j-1;
  26.         dir[RIGHT][i][j] = j+1;
  27.       }
  28.     }
  29.  
  30.     ll ans = 0, sum = 0;
  31.     queue<pii> q, to_delete;
  32.     for (int i = 0; i < R; ++i) {
  33.       for (int j = 0; j < C; ++j) {
  34.         sum += mat[i][j];
  35.         int total = 0, rivals = 0;
  36.         for (int k = 0; k < 4; ++k) {
  37.           int i2 = i+dr[k], j2 = j+dc[k];
  38.           if (i2 < 0 || i2 >= R || j2 < 0 || j2 >= C) continue;
  39.           total += mat[i2][j2], ++rivals;
  40.         }
  41.         if (rivals > 0 && total > mat[i][j]*rivals) {
  42.           to_delete.push({i, j});
  43.         }
  44.       }
  45.     }
  46.     ans += sum;
  47.  
  48.     while (!to_delete.empty()) {
  49.       while (!to_delete.empty()) {
  50.         pii curr = to_delete.front(); to_delete.pop();
  51.         int i = curr.first, j = curr.second;
  52.         if (mat[i][j] == 0) continue;
  53.         for (int &i2 = dir[UP][i][j]; i2 >= 0; --i2)   if (mat[i2][j]) { q.push({i2, j}); break; }
  54.         for (int &i2 = dir[DOWN][i][j]; i2 < R; ++i2)  if (mat[i2][j]) { q.push({i2, j}); break; }
  55.         for (int &j2 = dir[LEFT][i][j]; j2 >= 0; --j2) if (mat[i][j2]) { q.push({i, j2}); break; }
  56.         for (int &j2 = dir[RIGHT][i][j]; j2 < C; ++j2) if (mat[i][j2]) { q.push({i, j2}); break; }
  57.         sum -= mat[i][j];
  58.         mat[i][j] = 0;
  59.       }
  60.  
  61.       while (!q.empty()) {
  62.         pii curr = q.front(); q.pop();
  63.         int i = curr.first, j = curr.second;
  64.         if (mat[i][j] == 0) continue;
  65.         int total = 0, rivals = 0;
  66.         for (int &i2 = dir[UP][i][j]; i2 >= 0; --i2)   if (mat[i2][j]) { total += mat[i2][j], ++rivals; break; }
  67.         for (int &i2 = dir[DOWN][i][j]; i2 < R; ++i2)  if (mat[i2][j]) { total += mat[i2][j], ++rivals; break; }
  68.         for (int &j2 = dir[LEFT][i][j]; j2 >= 0; --j2) if (mat[i][j2]) { total += mat[i][j2], ++rivals; break; }
  69.         for (int &j2 = dir[RIGHT][i][j]; j2 < C; ++j2) if (mat[i][j2]) { total += mat[i][j2], ++rivals; break; }
  70.         if (total > mat[i][j]*rivals) {
  71.           to_delete.push({i, j});
  72.         }
  73.       }
  74.       ans += sum;
  75.     }
  76.  
  77.     printf("Case #%d: %lld\n", t, ans);
  78.   }
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement