Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pii;
- int T, R, C;
- int dr[] = {0, 0, -1, 1};
- int dc[] = {-1, 1, 0, 0};
- vector<vector<int>> mat, dir[4];
- const int UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3;
- int main() {
- scanf("%d", &T);
- for (int t = 1; t <= T; ++t) {
- scanf("%d%d", &R, &C);
- mat.assign(R, vector<int>(C));
- for (int i = 0; i < 4; ++i) {
- dir[i].assign(R, vector<int>(C));
- }
- for (int i = 0; i < R; ++i) {
- for (int j = 0; j < C; ++j) {
- scanf("%d", &mat[i][j]);
- dir[UP][i][j] = i-1;
- dir[DOWN][i][j] = i+1;
- dir[LEFT][i][j] = j-1;
- dir[RIGHT][i][j] = j+1;
- }
- }
- ll ans = 0, sum = 0;
- queue<pii> q, to_delete;
- for (int i = 0; i < R; ++i) {
- for (int j = 0; j < C; ++j) {
- sum += mat[i][j];
- int total = 0, rivals = 0;
- for (int k = 0; k < 4; ++k) {
- int i2 = i+dr[k], j2 = j+dc[k];
- if (i2 < 0 || i2 >= R || j2 < 0 || j2 >= C) continue;
- total += mat[i2][j2], ++rivals;
- }
- if (rivals > 0 && total > mat[i][j]*rivals) {
- to_delete.push({i, j});
- }
- }
- }
- ans += sum;
- while (!to_delete.empty()) {
- while (!to_delete.empty()) {
- pii curr = to_delete.front(); to_delete.pop();
- int i = curr.first, j = curr.second;
- if (mat[i][j] == 0) continue;
- for (int &i2 = dir[UP][i][j]; i2 >= 0; --i2) if (mat[i2][j]) { q.push({i2, j}); break; }
- for (int &i2 = dir[DOWN][i][j]; i2 < R; ++i2) if (mat[i2][j]) { q.push({i2, j}); break; }
- for (int &j2 = dir[LEFT][i][j]; j2 >= 0; --j2) if (mat[i][j2]) { q.push({i, j2}); break; }
- for (int &j2 = dir[RIGHT][i][j]; j2 < C; ++j2) if (mat[i][j2]) { q.push({i, j2}); break; }
- sum -= mat[i][j];
- mat[i][j] = 0;
- }
- while (!q.empty()) {
- pii curr = q.front(); q.pop();
- int i = curr.first, j = curr.second;
- if (mat[i][j] == 0) continue;
- int total = 0, rivals = 0;
- for (int &i2 = dir[UP][i][j]; i2 >= 0; --i2) if (mat[i2][j]) { total += mat[i2][j], ++rivals; break; }
- for (int &i2 = dir[DOWN][i][j]; i2 < R; ++i2) if (mat[i2][j]) { total += mat[i2][j], ++rivals; break; }
- for (int &j2 = dir[LEFT][i][j]; j2 >= 0; --j2) if (mat[i][j2]) { total += mat[i][j2], ++rivals; break; }
- for (int &j2 = dir[RIGHT][i][j]; j2 < C; ++j2) if (mat[i][j2]) { total += mat[i][j2], ++rivals; break; }
- if (total > mat[i][j]*rivals) {
- to_delete.push({i, j});
- }
- }
- ans += sum;
- }
- printf("Case #%d: %lld\n", t, ans);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement