题目链接:https://ac.nowcoder.com/acm/contest/403/A
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

现有一块n*m的地，每块1*1的地的高度为hi,j，在n*m的土地之外的土地高度均为0（即你可以认为最外圈无法积水）
现在下了一场足够大的雨，试求出这块地总共积了多少单位体积的水

输入描述

第一行两个数 n, m，具体含义见题意
接下来 n 行每行 m 个数, 第 i 行为 hi,1, hi,2, ..., hi,m

输出描述

输出一行一个数表示积水的总量。

输入

5 5
0 0 5 0 0
0 4 3 8 2
9 5 7 2 7
1 9 6 5 4
1 0 0 6 2
10 10
0 0 0 0 0 0 0 0 0 0
0 5 2 6 4 3 1 7 8 0
0 6 4 2 3 5 1 4 6 0
0 3 6 4 1 2 4 7 8 0
0 2 5 5 1 2 3 4 4 0
0 2 3 1 5 4 4 1 4 0
0 4 1 2 3 4 5 2 1 0
0 7 5 5 1 5 4 5 7 0
0 1 3 5 5 4 6 8 7 0
0 0 0 0 0 0 0 0 0 0

输出

4
23

备注:

- 对于10%的数据, n, m ≤ 4, h ≤ 5;
- 对于前50%的数据, n, m ≤ 20, h ≤ 10;
- 对于前70%的数据, n, m ≤ 100, h ≤ 50;
- 对于另外10%的数据, 不存在两个连续的块能积水;
- 对于95%的数据, n, m ≤ 500, h ≤ 100.
- 对于100%的数据, n, m ≤ 1000, h ≤ 1000,000,000.

解题思路

一个位置能存下多少水是由四周最低的柱子高度决定的，所以我们先把边缘位置的高度存起来，然后找出最低的，每次都从最低的边界向内部注水(仅与边界相邻的内部)，推出四周四个位置的水高度，如果发现高度比本位置低的就说明此位置最高的水位就是本位置的高度，比本位置高的说明存不下水。然后把注水后的柱子当作新的边界，也就是把边界放到一个优先队列中，每次都让高度最小的边界出队(优先队列)。

#include <bits/stdc++.h>
const int MAXN = 1005;
using namespace std;
struct edge {
    int x, y, h;
    friend bool operator < (edge a, edge b) {
        return a.h > b.h;
    }
}u;
int n, m, vis[MAXN][MAXN], mp[MAXN][MAXN];
int arr[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool Judge(int x, int y) {
    if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y])
        return true;
    return false;
}
priority_queue <edge> Q;
int main() {
    long long ans;
    while (~scanf("%d%d", &n, &m)) {
        ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                vis[i][j] = 0;
                scanf("%d", &mp[i][j]);
                if (!i || !j || i == n - 1  || j == m - 1) {
                    vis[i][j] = 1;
                    Q.push((edge){i, j, mp[i][j]});
                }
            }
        }
        while (!Q.empty()) {
            u = Q.top();
            Q.pop();
            for (int i = 0; i < 4; i++) {
                int tx = u.x + arr[i][0];
                int ty = u.y + arr[i][1];
                if (Judge(tx, ty)) {
                    vis[tx][ty] = 1;
                    if (u.h > mp[tx][ty]) {
                        ans += 1ll * (u.h - mp[tx][ty]);
                        mp[tx][ty] = u.h;
                    }
                    Q.push((edge){tx, ty, mp[tx][ty]});
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}