把积水高度写成逃逸水位减地形高度,逃逸水位是从格子走到外围的 minimax 路径,用多源 Dijkstra 从边界一次算完。
OJ: roj
题目 ID: 1687
难度:提高
标签:图论最短路堆python
创建: 2026-10-07 15:29
更新: 2026-10-07 15:29
形式化题目
给一个
把矩阵外面看作一块高度为
把它写成可计算的量:对每个格子
其中
以题面样例为例:
地形高度 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中间那一格
正解
思路
朴素做法。 最直接的是模拟:先让所有格子按自身高度持水,然后反复扫全图,
把「水面高于某个邻居地形」的水挪出去,直到不再变化。每一轮
关键观察:水位是个全局量,等于 minimax 路径。 水往低处流,能流多远只取决于路上最高的那道坎。
于是每格的水面最终会稳定在「逃出去所必须翻过的最高地形」的最低值上,也就是上面定义的
- 水位不会超过
。 取到 的那条路径 上,每个格子的地形都不超过 。 若某格水面高过 ,高出 的那部分水顺着 一路都能找到低于水面的地形, 最后流到外围消失;雨一直下也只是让它稳定在 ,不会更高。 - 水位不会低于
。 从 到外围的每条路径上,都有地形高度 的格子, 否则这条路径的最大值更小、 还能再降。这些「坝」把 围在里面, 水面在 以下的水没有出口,雨不停就只能继续涨。
所以答案就是
把 Dijkstra 的距离改成「路径最大高度」。 普通 Dijkstra 求
- 松弛单调:新键不小于当前键,所以一个格子一旦被弹出,就不可能再被更小的键刷新。
- 出堆即定型:设堆顶是
。若 还存在更优路径,取这条路径上第一个尚未定型的格子 , 它前面的格子都已定型、且已经用 松弛过 ,于是 早已带着不超过该值的键进了堆; 堆顶是全局最小值,矛盾。
于是照抄 Dijkstra 骨架,只把松弛的加法换成取
多源与虚拟外围。 边界格子一步就能跨进高度
入堆: 所有边界格子, 键 = max(h, 0)
弹堆顶 u(第一次弹出即定型)
对每个邻居 v: 若 max(dist[u], h[v]) < dist[v] 则更新并入堆
输出: 每格 dist[i][j] - h[i][j]用样例追一遍:初始堆里是边界八个格子的水位
代码
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++ 版(同一算法):
/**
* 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 的复杂度
。每个格子最多被改进若干次、每次入堆 , 时约 个格子,C++ 实测 秒、Python 实测 秒(限时 1000 ms)。 - 空间:地形、水位各一个
的表,加上定型标记与堆, ; 每个格子的水位是绝对值不超过 的整数,用 long long存不会溢出。 - 与 Python 版的关系:两版是同一算法,Python 用
heapq维护小根堆、(水位, 行, 列)三元组入堆, 同样靠「弹出时若键大于当前水位就跳过」做惰性删除。本题格子数不大,Python 不存在 TLE 风险。 - 边界情况:
或 时没有小块,按题目约定不输出任何内容; 时唯一格子是边界格子,答案 ,负高度得到正积水。
总结
- 先想清楚「水面停在哪里」,再想怎么算。 积水高度不是局部量:一个格子能存多少水, 由它到外围所有路径上最高的那道坎决定,这个量就是 minimax 路径值。
- minimax 是「换一种运算」的最短路。 Dijkstra 的正确性只依赖松弛单调不减,
把
换成 后骨架完全不变; 这类问题也常被叫作最小瓶颈路。 - 外围补一个高度
的虚拟源。 边界格子的初值取 , 正好把「跨出最后一步要越过高度 」这一件事编码进多源起点里,省掉所有特判。 - 负高度要单独留意。 因为水位下界是外围的
,高度为负的格子一定有水, 积水至少是 ;这也是数据里「一半数据保证高度非负」那一半之外最容易写错的地方。 - 本题是经典问题「二维接雨水」(LeetCode 407)的推广:那边外围也是一圈高度
的边界, 做法完全一样;一维版本则是把「路径」换成「左右两侧的最大值取较小者」。