思路与算法

每个格子的稳定水位是逃到外围所需跨越的最小瓶颈高度。外围高度固定为0，所以负高度边缘格也必须先填到0才能向外溢出。为此增加一个外围顶点。

相邻格之间连边，权为max(0,h[u],h[v])；每个边缘格与外围连边，权为max(0,h[u])。从外围到格子u的一条路径，其最大边权就是该路径上的最高地形与0的最大值。所求水位因此等于这些路径中最小的最大边权。

代码按边权排序，用并查集拒绝成环边，构造Kruskal最小生成树。在树上从外围出发遍历，令level[child]=max(level[parent],边权)。最后输出level[u]-h[u]，这是积水深度。零行或零列时直接按空矩阵输出，不做图计算。

正确性说明

对任一格u，若水位低于所有通外路径的瓶颈，就没有可供水流越过的通道，持续降雨会使水位继续上升；到达最小瓶颈后存在泄水通道，不能再稳定高于它。因此稳定水位是最小瓶颈值。路径包含外围0和当前格高度，所以所得水位至少为0且不低于当前地形，差值非负。

下面证明最小生成树可求该瓶颈。设树上外围到u路径的最大边权为B，取一条取得此值的边e。删掉e后，外围和u分属两个连通部分。任何原图通外路径都必须跨越该割。如果存在权小于B的跨割边，就能替换e而得到总权更小的生成树，与最小生成树性质矛盾。因此任意通外路径的最大边权至少为B；而树路径本身就达到B，所以B恰为最小瓶颈。

Kruskal按升序选取跨并查集连通块的边，是安全的割最小边选择，得到最小生成树。树遍历准确累积路径最大权，结合瓶颈结论得到正确水位，减去地形高度即为题目要求的积水深度。

复杂度

令V=nm，正尺寸时图有V+1个顶点、O(V)条边。建边、初始化并查集及树数组O(V)，排序O(V log(V+1))，并查集合并O(Valpha(V))，树遍历和输出O(V)。总时间O(V log(V+1))，额外空间O(V)。零尺寸只输出对应空行。高度、边权在int范围，水位与高度相减使用long long；最高积水深度可达2*10^9。

易错点

1. 外围是高度0，不是负无穷。样例右下角高度-1仍有1单位积水。
2. 输出积水深度，不是绝对水位，也不是全图总积水量。
3. 四方向相连，不能走对角线。
4. 负地形和零维度都是原题允许的输入，不擅自收紧为正高度或正尺寸。
5. 最小生成树路径用最大边累积，不是路径边权求和。
6. 覆盖正高边界包围负低内部、全负300乘300、随机正负1e9、单行单列及零维矩阵。

参考代码（C++11）

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
struct Edge {
    int a, b, w;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    int V = n * m;
    vector<int> h(V);
    for (int &x : h)
        cin >> x;
    if (!V) {
        for (int i = 0; i < n; ++i)
            cout << '\n';
        return 0;
    }
    vector<Edge> e;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            int u = i * m + j;
            if (i + 1 < n)
                e.push_back({u, u + m, max(0, max(h[u], h[u + m]))});
            if (j + 1 < m)
                e.push_back({u, u + 1, max(0, max(h[u], h[u + 1]))});
            if (i == 0 || j == 0 || i + 1 == n || j + 1 == m)
                e.push_back({u, V, max(0, h[u])});
        }
    sort(e.begin(), e.end(), [](const Edge &a, const Edge &b) {
        return a.w < b.w;
    });
    vector<int> p(V + 1), sz(V + 1, 1);
    iota(p.begin(), p.end(), 0);
    auto find = [&](int u) {
        int r = u;
        while (p[r] != r)
            r = p[r];
        while (p[u] != u) {
            int v = p[u];
            p[u] = r;
            u = v;
        }
        return r;
    };
    vector<vector<pair<int, int>>> tree(V + 1);
    int used = 0;
    for (auto x : e) {
        int a = find(x.a), b = find(x.b);
        if (a == b)
            continue;
        if (sz[a] < sz[b])
            swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        tree[x.a].push_back({x.b, x.w});
        tree[x.b].push_back({x.a, x.w});
        if (++used == V)
            break;
    }
    vector<long long> level(V + 1);
    vector<int> parent(V + 1, -1), stack{V};
    parent[V] = V;
    while (!stack.empty()) {
        int u = stack.back();
        stack.pop_back();
        for (auto x : tree[u])
            if (parent[x.first] < 0) {
                parent[x.first] = u;
                level[x.first] = max(level[u], (long long)x.second);
                stack.push_back(x.first);
            }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (j)
                cout << ' ';
            int u = i * m + j;
            cout << level[u] - h[u];
        }
        cout << '\n';
    }
}