打卡信奥刷题第2959天今天挑的是P5930 [POI 1999 R3] 降水。说真的第一眼看到这个题名的时候我还以为就是个二维前缀和的板子题毕竟“降水”嘛下个雨算个总量能有多难结果第一版代码跑完样例直接傻眼一个5x5的盆地手算都只有9我的程序却给我算出个乱七八糟的数。后来才明白这道波兰信息学奥林匹克1999年第三轮的题考的根本不是那个“面积”而是“水会从哪个缺口流走”。如果你正在准备CSP-J/S、NOIP或者刷题时对“二维接雨水”这种类型总觉得差一层窗户纸这篇就把题目翻译、算法思路、C实现和调试技巧一次讲透。1. 题目解读与核心思路拆解1.1 这题到底在问什么先按我的理解把题意梳理一遍。你拿到的是一个 R 行 C 列的网格每个格子上有一个整数高度 h[i][j]。下了一场足够大的雨之后水会自然往低处流低洼的地方就会积水——但是地图最外圈的格子是“边界”水到了边界就会直接流出去是存不住的。题目要你算的就是整张地图上一共积了多少水。注意一个很容易误会的点这里说的“积水量”不是水坑的面积而是水的体积。在网格模型里一个格子能积的水量 水面高度 - 这个格子的地面高度每格按 1x1 的面积算。比如一个 3x3 的地图四周边界都是 2中间一格是 0那中间就能积 2 个单位的水因为水面最高也只能到 2再高就从四周溢出去了。所以总量是 2。这就是整个问题最基本的模型。1.2 为什么“逐格灌水”和“前缀和”都搞不定拿到题我第一反应就是用二维前缀和。因为标题带“降水”网上又老有人提“信奥前缀和公式”我当时就想着先求个海拔总和再求个什么“隆起总量”一减不就完了试了之后立刻碰壁——前缀和能处理的是一维柱状图接雨水或者纯统计类问题它描述不了“水被谁挡住”这个依赖关系。二维地形里一个低洼格子的水位取决于它周围一整圈的最小边界这个最小边界根本不是一个连续的区间用前缀和算不出来。我第二反应是暴力“逐格灌水”把所有格子按高度排序从低到高一层层灌。听起来挺对水不就是先填最低的地方吗但问题是灌到某一层的时候哪些低洼区已经和边界连通了哪些还没有判断起来非常麻烦而且要反复合并连通块。我试着实现了一个带并查集的版本代码长度直接翻倍边界情况一堆最后一个样例还 WA 了。暴力不是不能做但比赛里写这种又长又容易错的代码性价比太低了。1.3 换个视角让水从外面“淹没”进来后来我换了个思路。既然判断“某个坑会不会积水”很麻烦不如不判断了直接把问题反过来假装水不是从天上掉下来的而是从地图外面不断往上涨从边界向内部“淹没”。水能淹到哪里、淹多深完全由它遇到的最低的“墙”决定。这样就把“找坑”变成了“沿着边界向内扩张”每个格子只会被处理一次逻辑一下子就顺了。这个视角其实对应着一个很经典的结论某个格子的最终水位等于从地图边界到该格子的所有路径中路径上最大高度值的最小值。换句话说就是“瓶颈路径”的最高点。你仔细品一下这个说法——水要到达这个格子必然要经过某一条路这条路上海拔最高的点决定了水能不能流过去而水会选那个最高点最低的路径走。这个“找最小瓶颈”的问题正好可以用优先队列 BFS 来解。2. 核心算法优先队列BFS的“木桶原理”2.1 木桶效应的正确打开方式很多人一看到“积水”就想到木桶效应一个坑能装多少水取决于它周围最低的那块木板。这个直觉没错但二维网格里的“木桶”不是一个固定的多边形而是一个动态的、不断变化的边界集合。核心问题变成了怎么高效地找到当前所有“墙”里最低的那一块答案就是最小堆优先队列。我们把所有边界格子当成初始的“墙”扔进堆里每次弹出高度最小的那块墙然后向它四周还没处理过的格子扩展。这里有一个非常关键的推理当前堆顶是所有墙的最低点所以水如果继续上涨一定会优先从这个位置漫出去。那么对于与它相邻的格子如果这个格子的地面比墙顶低它就会被水淹到“墙顶高度”积水量就是差值如果这个格子的地面比墙顶还高那它本身会成为新的墙原样入堆继续参与后续的“挡水”。这个算法本质上就是 Dijkstra 最短路的变体。你把每个格子的高度看成节点的基础权值堆顶弹出的值就是“到达该格子的最小瓶颈”答案就是累计所有“瓶颈比地面高”的格子的差值。很多同学学最短路的时候觉得 Dijkstra 只会用在大图上其实这类“最小化最大值”的题目它一样是好用的工具。2.2 算法流程分步拆解我把完整流程拆成下面这几步照着写基本不会漏读入 R、C 和高度矩阵网格用二维数组存。遍历所有边界格子第一行、最后一行、第一列、最后一列标记为已访问并把它们的高度值入堆。只要堆不空就弹出堆顶 curcur 表示当前已经“接触到水”的最低的墙。枚举 cur 的四个邻居上下左右越界或已访问直接跳过如果邻居高度 cur.h说明这个邻居能被当前水位淹没答案累加 cur.h - 邻居高度然后把邻居以 cur.h 的高度入堆水的表面已经漫到 cur.h后续更高的墙要站在这个水位之上继续挡水如果邻居高度 cur.h说明它自己就是一块新墙直接以自身高度入堆。邻居入堆时顺手标记已访问。堆空之后ans 就是答案。这里最容易出错的点是为什么邻居被水淹没后要按 cur.h 而不是按邻居本来的高度入堆举个例子一个低洼格子的地面是 0周围最低墙是 2水填到 2 之后这个格子对外的“水位”就是 2。如果后面有个更高的墙在它旁边新墙的相对高度要站在“水位 2”上面来算。如果你按邻居本来的高度 0 入堆就可能让一个其实已经被水填平的低洼格子又被当成“低墙”处理水量就会算重或者算漏。这块我一开始写错过调了半小时才意识到。2.3 边界条件的魔鬼细节边界判断要特别小心。i 0 || i R-1 || j 0 || j C-1这四个条件写的时候注意行和列的下标不要混。曾经有同学把 R 和 C 抄反结果边界格子全判错了。另外当 R 或 C 等于 1 的时候整个地图就是一条“沟”水从两侧或者首尾直接流走积水量一定是 0。用这个算法跑一遍也能得到正确答案因为所有格子本身都是边界全部入堆后没有内部格子可以扩展ans 自然为 0。不需要单独特判但不能把这种特殊情况排除在外否则数组越界。还有一点让我吃了大亏答案必须用long long不要用int。R、C 到千级别高度如果到十万百万一个低洼格子的积水量可能就是九位数R*C 个格子累加之后很容易超过 2^31。我当时用 int 存答案本地小样例全过交上去 WA 一个点排查了半天才发现是溢出了。3. C完整实现与核心代码解析3.1 数据结构与读入的顺序陷阱先说我踩过的一个坑P5930 在洛谷上的读入是“先读行数 n再读列数 m”然后接着读 n 行、每行 m 个高度。看起来没什么但如果你之前做过别的题或者习惯先读列再读行就很容易把 n 和 m 当成一样的变量来用。我建议读入之后立刻把数组开成vectorvectorint a(n, vectorint(m))并且把n固定理解为行数、m固定理解为列数后续所有循环都按这个来不要中途换。我用的开发环境是 VS Code 配好了 C 编译链编译时开 C17这份代码直接复制就能跑。结构体我习惯这样写三个字段分别存行、列、当前“水位高度”。注意这里存的“高度”不是原始地面高度而是“如果这个格子已经接触到水的话水的表面高度”。这个设计是整段代码的灵魂。3.2 核心代码逐段解读直接上一份可编译的完整代码我加了注释后面再逐段说#include bits/stdc.h using namespace std; struct Node { int x, y, h; }; struct cmp { bool operator()(const Node a, const Node b) { return a.h b.h; // 小顶堆堆顶是最低的墙 } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorint a(n, vectorint(m)); for (int i 0; i n; i) for (int j 0; j m; j) cin a[i][j]; priority_queueNode, vectorNode, cmp pq; vectorvectorbool vis(n, vectorbool(m, false)); 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) { pq.push({i, j, a[i][j]}); vis[i][j] true; } } } int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; long long ans 0; while (!pq.empty()) { Node cur pq.top(); pq.pop(); for (int d 0; d 4; d) { int nx cur.x dx[d]; int ny cur.y dy[d]; if (nx 0 || nx n || ny 0 || ny m) continue; if (vis[nx][ny]) continue; vis[nx][ny] true; if (a[nx][ny] cur.h) { ans cur.h - a[nx][ny]; pq.push({nx, ny, cur.h}); } else { pq.push({nx, ny, a[nx][ny]}); } } } cout ans \n; return 0; }拆开说几个关键点。自定义比较器cmp里我写的是a.h b.h这行代码决定了堆顶是最小的元素。很多人记不住 priority_queue 默认是大顶堆老是写反把最大的弹出来结果整个算法直接变成“从最高的墙开始灌水”输出完全错误。我自己写的时候也会在这里打个标记防止犯迷糊。入堆的时机是重点边界格子和每一个被访问到的邻居都是入堆的瞬间就标记vis。很多初次接触这个算法的人会习惯在pq.pop()的时候标记觉得“处理到它才算访问过”结果同一个格子被四个邻居各入堆一次堆越来越大最后要么超时要么算错。记住一个原则只要它进了堆就说明它已经被“墙”接纳了不能再被别的方向重复接纳。if (a[nx][ny] cur.h)这个分支是整道题的唯一考点。有人问为什么相等的时候不积水因为相邻格子高度等于水位时它正好露出了水面本身就能当墙用自然不产生水量。也有人问如果邻居是一个更低洼格子的入口我们只救了它一个它背后的大坑怎么办不用担心这个邻居以cur.h的高度入堆后会被继续弹出并向它的邻居扩展积水过程会像波浪一样一层层扩散到整个坑每个格子都只被处理一次总量正好是全部低洼格子的差值之和。为了验证代码正确性我跑了一下洛谷的样例。输入是 5 行 5 列、四周一圈 1、内部 3x3 全是 0 的盆地程序输出 9和手算一致。这说明从边界向内扩张的顺序是对的四个角先入堆然后一圈边界互相扩展最后把内部九个格子逐个淹没每个格子淹了 1 个单位的水。3.3 复杂度分析与空间优化时间复杂度是 O(n*m*log(n*m))堆的每次插入和弹出都是对数级每个格子至多入堆一次所以总规模就是网格大小乘上对数。n、m 在千级别时这个复杂度完全能跑进一秒多。空间上我们用了两个 n*m 的二维数组一个存高度、一个存访问标记再加上堆里最多同时存在的 O(n*m) 个节点总空间是 O(n*m)不存在爆内存的风险。如果想省一点常数可以用pairint, pairint,int来代替结构体把高度放第一位然后存入负高度来模拟小顶堆。不过说实话竞赛里可读性比这点常数重要结构体加自定义比较器已经足够了。真要优化不如把vis数组改成vectorvectorchar省得vectorbool的位压缩在一些老编译器上有奇怪的性能问题实测在数据量大的时候能快那么一点。4. 常见错误、调试技巧与经验总结4.1 常见错误速查表我把刷这道题时容易踩的坑整理成一张表提交前对照自查一遍能省很多冤枉时间错误类型典型现象原因与解法vis 标记时机搞错堆无限膨胀内存爆炸或超时入堆时立刻标记不要等弹出再标记答案用 int 存小样例全对大数据 WA累计水量可能超 int必须用 long long行列读反样例能过但边界判定错乱固定 n 为行、m 为列别中途换含义堆顶方向搞反输出远大于答案priority_queue 默认大顶堆自定义 cmp 要返回 a.h b.h邻居高度相等时不处理明明等高却多算了水高度相等说明露在水面外按“墙”处理才对边界只入堆不标记访问边界格子被重复处理入堆和标记必须成对出现4.2 调试技巧把“淹没过程”画出来这个算法最大的特点是“过程直观但代码不好查错”。我强烈建议在一个小样例上手动跑一遍堆的变化过程。比如这个 3x3 的图2 2 2 2 0 2 2 2 2全部边界先入堆堆里八个 2。第一次弹出任意一个 2它周围的格子要么是边界已经访问要么是中间的 0。发现 0 2于是ans 2中间格子以高度 2 入堆。之后再弹出什么都是 2中间格子四周全是边界不会再产生水量。最后 ans 2和手算一致。如果算出来不是这个数那基本可以断定是堆顶方向、入堆时机或者标记的问题。再教大家一个土办法在代码里临时写个debug()函数每次弹出堆顶时输出当前格子的坐标、高度和当前 ans。跑样例时观察弹出的顺序看看是不是“从低到高”地在扩张。如果弹出的顺序忽高忽低说明优先队列写错了或者有格子被重复塞进去了。我当时就是这么发现自己的vis标记写晚了的——堆里同一个格子出现了三次弹出的高度序列乱七八糟。4.3 通用套路这类“水题”的识别特征刷题刷多了你会发现“降水”这种题根本不是一个孤立的题。凡是你看到“网格 高度 积水”三个关键词第一反应就应该是优先队列 BFS如果题目变成一维柱状图求接水量那才用单调栈或者双指针如果题目变成水位随时间变化或者多个出口就可能要套用并查集离线处理了。这道 P5930 和 LeetCode 407 的接雨水 II 几乎一模一样你在别的题库里还能看到它的各种变体比如把“水”换成“熔岩”、“沙丘”核心都是同一个最小瓶颈模型。我个人的经验是遇到这种“先入为主的算法失效”的题不要急着改代码先把问题的思维模型换掉。一维的前缀和、二维的优先队列扩张、并查集维护动态连通性这些都是工具箱里的不同扳手关键是判断当前这个螺丝该用哪一个。判断标准就一条约束是局部的还是全局的。积水问题里每个格子的水位由整圈边界决定这是全局约束所以局部的前缀和注定帮不上忙。最后说点个人体会。刷到第 2959 天我越来越觉得P5930 这种二十多年前的老题价值根本不在“难”而在它逼着我把“水往低处流”这句朴素直觉翻译成一套严格的不变量。写这题的时候我踩过最蠢的坑就是忘了入堆时标记 visited导致同一个格子被重复推进堆里程序跑得比蜗牛还慢。后来我把“入堆即标记”四个字写在题解本子第一页之后遇到所有 BFS 变种题都没再犯过。如果你也被这道题卡过希望这篇能帮你省下我当时调试的那几个小时。下次再看到“降水”这两个字别急着开前缀和数组先想想水会从哪个缺口流走