积水问题

GitHub跳转原题关系图返回列表

把积水高度写成逃逸水位减地形高度,逃逸水位是从格子走到外围的 minimax 路径,用多源 Dijkstra 从边界一次算完。

OJ: roj

题目 ID: 1687

难度:提高

标签:图论最短路堆python

创建: 2026-10-07 15:29

更新: 2026-10-07 15:29

形式化题目

给一个 n×mn \times m 的整数矩阵 hh(h[i][j]h[i][j] 是第 ii 行第 jj 列小块的地形高度,可正可负可零)。 格子之间按四邻接相连,水只能沿边流向四邻居。

把矩阵外面看作一块高度为 00 的、无限大的虚拟区域,它与每个边界格子相邻,水流入其中就消失。 一场不停的雨落下后,水在低洼处积起来,直到每格的水面高度不再上升。求最终每个格子的积水高度 (水面高度减去地形高度)。

把它写成可计算的量:对每个格子 (i,j)(i,j),定义它的逃逸水位

L(i,j)  =  min⁡P : (i,j)→外围  max⁡(0, max⁡(x,y)∈Ph[x][y]), L(i,j) \;=\; \min_{P\,:\,(i,j) \to \text{外围}} \;\max\Bigl(0,\ \max_{(x,y) \in P} h[x][y]\Bigr),

其中 PP 取遍所有「从 (i,j)(i,j) 出发、每步走四邻居、最终抵达某个边界格子并跨入外围」的路径, 路径上的最大值里那个 00 就是跨入外围的最后一步。答案是

w(i,j)  =  L(i,j)−h(i,j)  ⩾  0. w(i,j) \;=\; L(i,j) - h(i,j) \;\geqslant\; 0 .

以题面样例为例:

text
地形高度 h          逃逸水位 L          积水高度 L - h
 4  4  0             4  4  0             0  0  0
 2  1  3             2  2  3             0  1  0
 3  3 -1             3  3  0             0  0  1

中间那一格 (1,1)(1,1) 高 11,四个邻居的高度是 4,2,3,34, 2, 3, 3。往右、往下都要翻过 33 的坎, 只有往左经过高度 22 的 (1,0)(1,0) 再出界最省,于是 L(1,1)=2L(1,1) = 2、积水 11。 右下角 (2,2)(2,2) 高 −1-1,它本身就是边界格子,L=max⁡(−1,0)=0L = \max(-1, 0) = 0、积水 11。 注意水位 LL 恒不小于 00(外围高度是 00),所以高度为负的格子一定有水,积水至少是 −h[i][j]-h[i][j]。

正解

思路

朴素做法。 最直接的是模拟:先让所有格子按自身高度持水,然后反复扫全图, 把「水面高于某个邻居地形」的水挪出去,直到不再变化。每一轮 O(nm)O(nm),但收敛轮数无法控制, 300×300300 \times 300 下不可接受。另一个朴素做法是对每个格子二分水位 tt,再用一次 BFS 检查 「只走 h⩽th \leqslant t 的格子能不能摸到边界」,单格 O(nmlog⁡V)O(nm \log V),全图 O(n2m2log⁡V)O(n^2m^2 \log V),同样太慢。

关键观察:水位是个全局量,等于 minimax 路径。 水往低处流,能流多远只取决于路上最高的那道坎。 于是每格的水面最终会稳定在「逃出去所必须翻过的最高地形」的最低值上,也就是上面定义的 L(i,j)L(i,j)。 两侧都不难想清楚:

  • 水位不会超过 L(i,j)L(i,j)。 取到 L(i,j)L(i,j) 的那条路径 PP 上,每个格子的地形都不超过 L(i,j)L(i,j)。 若某格水面高过 L(i,j)L(i,j),高出 L(i,j)L(i,j) 的那部分水顺着 PP 一路都能找到低于水面的地形, 最后流到外围消失;雨一直下也只是让它稳定在 L(i,j)L(i,j),不会更高。
  • 水位不会低于 L(i,j)L(i,j)。 从 (i,j)(i,j) 到外围的每条路径上,都有地形高度 ⩾L(i,j)\geqslant L(i,j) 的格子, 否则这条路径的最大值更小、L(i,j)L(i,j) 还能再降。这些「坝」把 (i,j)(i,j) 围在里面, 水面在 L(i,j)L(i,j) 以下的水没有出口,雨不停就只能继续涨。

所以答案就是 L(i,j)−h(i,j)L(i,j) - h(i,j),问题化成:求每个格子的「路径最大高度」的最小值。

把 Dijkstra 的距离改成「路径最大高度」。 普通 Dijkstra 求 min⁡∑\min \sum 边权, 这里要求的是 min⁡max⁡\min \max,但 Dijkstra 的成立条件只用到「松弛不会让键变小」这一条:

nd=max⁡(dist[u], h[v])  ⩾  dist[u]. \texttt{nd} = \max(\texttt{dist}[u],\ h[v]) \;\geqslant\; \texttt{dist}[u] .
  • 松弛单调:新键不小于当前键,所以一个格子一旦被弹出,就不可能再被更小的键刷新。
  • 出堆即定型:设堆顶是 uu。若 uu 还存在更优路径,取这条路径上第一个尚未定型的格子 vv, 它前面的格子都已定型、且已经用 max⁡\max 松弛过 vv,于是 vv 早已带着不超过该值的键进了堆; 堆顶是全局最小值,矛盾。

于是照抄 Dijkstra 骨架,只把松弛的加法换成取 max⁡\max,复杂度与堆优化 Dijkstra 相同。

多源与虚拟外围。 边界格子一步就能跨进高度 00 的外围,所以它们的初始水位是 max⁡(h[i][j],0)\max(h[i][j], 0), 全部入堆当多源起点;内部的格子初始水位记成 +∞+\infty。跑完之后每个格子都拿到了 LL,输出 L−hL - h 即可。

text
入堆: 所有边界格子, 键 = max(h, 0)
弹堆顶 u(第一次弹出即定型)
  对每个邻居 v: 若 max(dist[u], h[v]) < dist[v] 则更新并入堆
输出: 每格 dist[i][j] - h[i][j]

用样例追一遍:初始堆里是边界八个格子的水位 4,4,0,2,3,3,3,04,4,0,2,3,3,3,0。 先弹两个键为 00 的边界格子 (0,2)(0,2)、(2,2)(2,2),它们把邻居的水位顶到 max⁡(0,h)\max(0, h); 接着弹 (1,0)(1,0)(键 22),它把唯一的内部格子 (1,1)(1,1) 的水位压到 max⁡(2,1)=2\max(2, 1) = 2 并入堆; (1,1)(1,1) 的键 22 比剩下的边界格子(键 3,3,3,4,43, 3, 3, 4, 4)都小,紧接着就被弹出定型, 积水 2−1=12 - 1 = 1。后面弹出的 (1,2)(1,2)、(2,0)(2,0)、(2,1)(2,1) 键都是 33,只会把 (1,1)(1,1) 试成 33,不改进。 三行输出与样例一致。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 15:29
# update_at: 2026-10-07 15:29

import heapq
import sys

INF = 1 << 62  # 哨兵:这个格子的逃逸水位还没被任何一条通往外围的路径确定

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Grid = list[list[int]]  # 地形高度或逃逸水位,Grid[i][j] 是第 i 行第 j 列


def escape_levels(n: int, m: int, height: Grid) -> Grid:
    """回答「每个格子逃到外围时水位最高要被抬到哪里」:所有路径中「路径最大地形高度」的最小值。"""
    level: Grid = [[INF] * m for _ in range(n)]
    heap = []  # 小根堆:(水位, 行, 列)
    for i in range(n):
        for j in range(m):
            if i in (0, n - 1) or j in (0, m - 1):  # 边界格子直接挨着高度 0 的外围
                level[i][j] = max(height[i][j], 0)
                heap.append((level[i][j], i, j))
    heapq.heapify(heap)

    while heap:
        d, i, j = heapq.heappop(heap)
        if d > level[i][j]:
            continue  # 过期堆项:这个格子已经被更小的水位定型过
        for ni, nj in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
            if 0 <= ni < n and 0 <= nj < m:
                nd = max(d, height[ni][nj])  # 走这条边,水位被沿途更高的地形顶起来
                if nd < level[ni][nj]:
                    level[ni][nj] = nd
                    heapq.heappush(heap, (nd, ni, nj))
    return level


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    if n == 0 or m == 0:  # 一块地都没有,没有输出
        return
    height = [[next(data) for _ in range(m)] for _ in range(n)]
    level = escape_levels(n, m, height)
    # 积水高度 = 逃逸水位 - 地形高度,恒非负
    print('\n'.join(' '.join(str(level[i][j] - height[i][j]) for j in range(m)) for i in range(n)))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 15:29
 * update_at: 2026-10-07 15:29
 */
// 1687 积水问题:二维接雨水的推广,外围是「无限大且高度为 0」的区域。
// 一个格子的积水高度 = 逃逸水位 - 地形高度,而逃逸水位是
// 「从该格子走到外围的所有路径上,路径最大地形高度」的最小值(minimax 路径)。
// 求 minimax 用多源 Dijkstra:所有边界格子以 max(h,0) 为初始水位入堆,
// 每次弹出水位最小的格子,向四个方向松弛 nd = max(当前水位, 邻居地形高度)。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 305;
const ll INF = (1LL << 62);

int n, m;              // 土地的行数、列数
ll h[MAXN][MAXN];      // h[i][j] 是第 i 行第 j 列小块的地形高度
ll level[MAXN][MAXN];  // level[i][j] 是逃逸水位:从 (i,j) 逃到外围的路径上最大高度的最小值
char done[MAXN][MAXN]; // 该格子的逃逸水位是否已经确定(Dijkstra 出堆标记)

const int di[4] = {1, -1, 0, 0};
const int dj[4] = {0, 0, 1, -1};

// 小根堆的结点:水位 d,格子编号 id = i * m + j
struct Node {
    ll d;
    int id;

    // priority_queue 默认大根堆,把比较反过来就得到小根堆
    bool operator<(const Node &other) const {
        return d > other.d;
    }
};

priority_queue<Node> pq;

// 多源 Dijkstra 求每个格子的逃逸水位
void solve() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            level[i][j] = INF;
            done[i][j] = 0;
        }
    }

    // 外围高度为 0,边界格子直接挨着外围,所以水位至少是 max(h, 0)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                level[i][j] = max(h[i][j], 0LL);
                pq.push(Node{level[i][j], i * m + j});
            }
        }
    }

    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();
        int i = cur.id / m;
        int j = cur.id % m;
        if (done[i][j]) continue; // 同一格子可能入堆多次,只处理水位最小的那一次
        done[i][j] = 1;

        for (int k = 0; k < 4; k++) {
            int ni = i + di[k];
            int nj = j + dj[k];
            if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
            if (done[ni][nj]) continue;
            ll nd = max(cur.d, h[ni][nj]); // 走这条边,水位被沿途更高的地形顶起来
            if (nd < level[ni][nj]) {
                level[ni][nj] = nd;
                pq.push(Node{nd, ni * m + nj});
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            printf("%lld%c", level[i][j] - h[i][j], j + 1 == m ? '\n' : ' ');
        }
    }
}

int main() {
    if (scanf("%d %d", &n, &m) != 2) return 0;
    if (n <= 0 || m <= 0) return 0; // 没有小块,没有输出
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%lld", &h[i][j]);
        }
    }
    solve();
    return 0;
}

复杂度

  • 时间:堆优化 Dijkstra 的复杂度 O(nmlog⁡(nm))O(nm \log(nm))。每个格子最多被改进若干次、每次入堆 O(log⁡(nm))O(\log(nm)), n=m=300n = m = 300 时约 9×1049 \times 10^4 个格子,C++ 实测 0.030.03 秒、Python 实测 0.130.13 秒(限时 1000 ms)。
  • 空间:地形、水位各一个 n×mn \times m 的表,加上定型标记与堆,O(nm)O(nm); 每个格子的水位是绝对值不超过 10910^9 的整数,用 long long 存不会溢出。
  • 与 Python 版的关系:两版是同一算法,Python 用 heapq 维护小根堆、(水位, 行, 列) 三元组入堆, 同样靠「弹出时若键大于当前水位就跳过」做惰性删除。本题格子数不大,Python 不存在 TLE 风险。
  • 边界情况:n=0n = 0 或 m=0m = 0 时没有小块,按题目约定不输出任何内容; n=m=1n = m = 1 时唯一格子是边界格子,答案 =max⁡(h,0)−h= \max(h, 0) - h,负高度得到正积水。

总结

  • 先想清楚「水面停在哪里」,再想怎么算。 积水高度不是局部量:一个格子能存多少水, 由它到外围所有路径上最高的那道坎决定,这个量就是 minimax 路径值。
  • minimax 是「换一种运算」的最短路。 Dijkstra 的正确性只依赖松弛单调不减, 把 dist[u]+w\texttt{dist}[u] + w 换成 max⁡(dist[u],h[v])\max(\texttt{dist}[u], h[v]) 后骨架完全不变; 这类问题也常被叫作最小瓶颈路。
  • 外围补一个高度 00 的虚拟源。 边界格子的初值取 max⁡(h,0)\max(h, 0), 正好把「跨出最后一步要越过高度 00」这一件事编码进多源起点里,省掉所有特判。
  • 负高度要单独留意。 因为水位下界是外围的 00,高度为负的格子一定有水, 积水至少是 −h[i][j]-h[i][j];这也是数据里「一半数据保证高度非负」那一半之外最容易写错的地方。
  • 本题是经典问题「二维接雨水」(LeetCode 407)的推广:那边外围也是一圈高度 00 的边界, 做法完全一样;一维版本则是把「路径」换成「左右两侧的最大值取较小者」。