Paste Search Dynamic
Recent pastes
solve
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5.  
  6. void solve() {
  7.         int r, c;
  8.         scanf(" %d %d", &r, &c);
  9.         int G[r][c];
  10.         for (int i = 0; i < r; ++i) {
  11.                 for (int j = 0; j < c; ++j) {
  12.                         scanf(" %d", &G[i][j]);
  13.                 }
  14.         }
  15.         priority_queue<pair<int,pair<int, int> > > q;
  16.         for (int i = 0; i < r; ++i) {
  17.                 for (int j = 0; j < c; ++j) {
  18.                         if (G[i][j]) q.push({G[i][j], {i,j}});
  19.                 }
  20.         }
  21.         ll res = 0;
  22.         int di[4] = {0,1, 0,-1};
  23.         int dj[4] = {1,0,-1, 0};
  24.         while(!q.empty()) {
  25.                 auto p = q.top(); q.pop();
  26.                 int h = p.first, ii = p.second.first, jj = p.second.second;
  27.                 for (int l = 0; l < 4; ++l) {
  28.                         int i = ii + di[l], j = jj + dj[l];
  29.                         if (i >= 0 && i < r && j >= 0 && j < c) {
  30.                                 if (h-1 > G[i][j]) {
  31.                                         res += (h - 1 - G[i][j]);
  32.                                         G[i][j] = h-1;
  33.                                         q.push({G[i][j], {i, j}});
  34.                                 }
  35.                         }
  36.                 }
  37.         }
  38.         printf("%lldn", res);
  39.  
  40. }
  41.  
  42. int main() {
  43.         int t;
  44.         scanf(" %d", &t);
  45.  
  46.         for (int i = 1; i <= t; ++i) {
  47.                 printf("Case #%d: ", i);
  48.                 solve();       
  49.         }
  50.        
  51. }
Parsed in 0.009 seconds