Loading

WATER

  1. #include <iostream>
  2. #include <queue>
  3. #include <cstring>
  4.  
  5. using namespace std;
  6.  
  7. struct node {
  8.     int h;
  9.     int x;
  10.     int y;
  11.  
  12. };
  13.  
  14. bool operator<(const struct node& a, const struct node &b) {
  15.     return a.h > b.h;
  16. }
  17.  
  18. node make_node(int h, int x, int y) {
  19.     node n = {h, x, y};
  20.     return n;
  21. }
  22.  
  23. int arr[101][101];
  24. bool visited[101][101];
  25.  
  26. int main() {
  27.     int T;
  28.     cin >> T;
  29.     while(T--) {
  30.         int N, M;
  31.         cin >> N >> M;
  32.         priority_queue<struct node> pq;
  33.         for(int i = 0; i < N; i++) {
  34.             for(int j = 0; j < M; j++) {
  35.                 cin >> arr[i][j];
  36.                 node n = make_node(arr[i][j], i, j);
  37.                 if(i == 0 || j == 0 || i == N - 1 || j == M - 1) {
  38.                     if((i == 0 && j == 0) ||
  39.                        (i == 0 && j == M - 1) ||
  40.                        (i == N - 1 && j == 0) ||
  41.                        (i == N - 1 && j == M - 1)) {
  42.                         continue;
  43.                     }
  44.                     pq.push(n);
  45.                     visited[i][j] = true;
  46.                 }
  47.             }
  48.         }
  49.         visited[0][0] = true;
  50.         visited[0][M - 1] = true;
  51.         visited[N - 1][0] = true;
  52.         visited[N - 1][M - 1] = true;
  53.         long long ans = 0;
  54.         while(!pq.empty()) {
  55.             struct node front = pq.top();
  56.             //cout << "front debug" << endl;
  57.             //cout << front.h << " " << front.x << " " << front.y << endl;
  58.             pq.pop();
  59.             int dx[4] = {1, -1, 0, 0};
  60.             int dy[4] = {0, 0, 1, -1};
  61.  
  62.             // bfs from the top and try to flood fill
  63.             queue<struct node> q;
  64.             q.push(front);
  65.             while(!q.empty()) {
  66.                 struct node f = q.front();
  67.                 //cout << "f debug" << endl;
  68.                 //cout << f.h << " " << f.x << " " << f.y << endl;
  69.                 q.pop();
  70.                 visited[f.x][f.y] = true;
  71.  
  72.                 for(int i = 0; i < 4; i++) {
  73.                     int X = f.x + dx[i];
  74.                     int Y = f.y + dy[i];
  75.                     if(X >= 1 && X < N - 1 && Y >= 1 && Y < M - 1 && !visited[X][Y]) {
  76.                         if(arr[X][Y] <= f.h) {
  77.                             ans += - arr[X][Y] + f.h;
  78.                             arr[X][Y] = f.h;
  79.                             q.push(make_node(arr[X][Y], X, Y));
  80.                             visited[X][Y] = true;
  81.                         }
  82.                         else {
  83.                             pq.push(make_node(arr[X][Y], X, Y));
  84.                         }
  85.                     }
  86.                 }
  87.             }
  88.         }
  89.         cout << ans << endl;
  90.     }
  91.     return 0;
  92. }