分析

• 这里的水只能向上下左右四个方向流动，是四连通的。

• 这一题是Leetcode 0042 接雨水的一个三维版本，而和Leetcode 0407 接雨水 II是一样的，这里认为Leetcode 0042 接雨水是一个二维版本。

• Leetcode 0042 接雨水只需要求解左右两条路径中的最大高度的最小值即可，这一题的代码如下：

class Solution {
public:
    int trap(vector<int> &height) {

        int n = height.size();
        if (n == 0) return 0;

        vector<int> left_max(n), right_max(n);

        left_max[0] = height[0];
        for (int i = 1; i < n; i++) left_max[i] = max(left_max[i - 1], height[i]);
        right_max[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) right_max[i] = max(right_max[i + 1], height[i]);

        int res = 0;
        for (int i = 0; i < n; i++) res += min(left_max[i], right_max[i]) - height[i];

        return res;
    }
};

• 和Leetcode 0042 接雨水的做法类似，我们需要找到从当前位置到达大海的所有路径中的最大值的最小值（从该点到大海有多条路径，每条路径都有一个最大值，我们需要在这些最大值中找到最小的那一个），这个最小值就是下雨后该点的高度。

• 类似于最短路问题，最短路问题是求解路径总和的最小值；这里的问题是求出所有路径中最大值的最小值。这一题可以采用最短路径的方式求解，下面使用dijkstea算法求解该问题。

• 本题的起点可以设为大海，相当于新建了一个虚拟源点s。从s向四周的每个格子都连接一条边权为0的边，所有起点不能到达的点标记为正无穷，然后从s求单源最短路径即可（从a走到b的边权定义为b所在位置的高度）。

• 代码实现时不需要真实地将s建立出来，直接将s到达的所有点加入优先队列即可。

• 设$dist[i][j]$表示从s到$(i, j)$所有路径中边权最大值的最小值，如果从$(i, j)$能到达$(x, y)$，则根据定义一定有：$dist[x][y] \le max(dist[i][j], h[x][y])$。解释如下：

• 下面还有一个问题，就是要证明一下可以使用dijkstea算法求解该问题。核心是证明当前从优先队列中出队的元素（假设是$(x, y)$）就是最小值，不可能被其他点更新了。可以用反证法证明，假设当前队首元素会被更新成更小的数据，则一定是被队列中后面的点（假设是$(i, j)$）更新，但是从源点到后面的点的值更大，根据$dist[x][y]$一定是被$max(dist[i][j], h[x][y])$，这里是取大，所以当前队首元素不可能被更新的更小。

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 55;

int n, m;  // 行数、列数
int h[N][N];  // 高度
int dist[N][N];  // dist[i][j]表示到达(i, j)的所有路径中边权最大值的最小值
bool st[N][N];  // 堆优化版的dijkstra算法中判重数组, 为true代表该点已经求出答案
int res;  // 最终存储水的总量

struct Node {
    int x, y, d;  // d: 到达(x, y)的所有路径中边权最大值的最小值
    bool operator< (const Node &t) const {
        return d > t.d;  // 默认大顶堆，需要使用小顶堆
    }
};

void dijkstra() {

    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    res = 0;

    priority_queue<Node> heap;

    // 将四周的点加入优先队列
    for (int i = 1; i <= n; i++) {
        heap.push({i, 1, h[i][1]});
        dist[i][1] = h[i][1];
        heap.push({i, m, h[i][m]});
        dist[i][m] = h[i][m];
    }
    for (int i = 2; i < m; i++) {
        heap.push({1, i, h[1][i]});
        dist[1][i] = h[1][i];
        heap.push({n, i, h[n][i]});
        dist[n][i] = h[n][i];
    }

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (heap.size()) {

        Node t = heap.top(); heap.pop();

        if (st[t.x][t.y]) continue;
        st[t.x][t.y] = true;

        res += t.d - h[t.x][t.y];

        for (int i = 0; i < 4; i++) {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x < 1 || x > n || y < 1 || y > m) continue;
            if (dist[x][y] > max(t.d, h[x][y])) {  // (t.x, t.y)到(x, y)的边权为h[x][y]
                dist[x][y] = max(t.d, h[x][y]);
                heap.push({x, y, dist[x][y]});
            }
        }
    }
}

int main() {

    int T;
    scanf("%d", &T);
    for (int C = 1; C <= T; C++) {

        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &h[i][j]);

        dijkstra();

        printf("Case #%d: %d\n", C, res);
    }

    return 0;
}