信奥刷题打卡到第2959题这次做的是P5930 [POI 1999 R3] 降水。这道题在洛谷上难度不算爆炸但卡住过不少选手。我第一次拿到时下意识套一维接雨水的单调栈模板结果样例都过不去。后来认真想了半天才意识到二维地形里的水不是从左右两个方向憋出来的而是从整圈边界往内部漫的。这篇笔记就把我最终采用的优先队列BFS写法、暴力分层对比、以及调试对拍过程中踩过的坑一起整理出来。适合正在备赛信奥提高组、省选或者想补二维图论建模的读者看完应该能直接AC。1. 先把题意吃透降水问题到底在算什么1.1 一维接雨水和二维降水的本质差异一维版接雨水题目大家很熟给定一个高度数组每个位置能存多少水等于min(左侧最大高度, 右侧最大高度) - 自身高度。这个题在信奥入门里属于“必背”做法也很多双指针、单调栈都能写。但 P5930 的“降水”不是一维接雨水的简单扩展。它是一个n x m的矩形棋盘a[i][j]表示第 i 行第 j 列的地面海拔。降水落在每个格子上水可以在相邻四个方向流动最终通过边界流出。题目要输出积水总体积也就是所有格子积水深度之和。为什么不能直接把一维办法拿过来用因为一维中一个位置的水位只由左右两堵最高墙决定中间怎么绕都是直线路径。二维里面“墙”不止两根水可以选择上下左右任意方向流走。一个低洼盆地只要在某一侧出现一条由较低地面连到边界的通道水就会顺着通道流出去一滴都存不住。所以二维模型必须考虑路径和连通性而不是简单的两侧最值。这也就是很多选手第一次做这题懵掉的原因一维逻辑根深蒂固总觉得某个格子只要“四周都高”就能蓄水。实际上“四周都高”还不够必须保证这个高墙围出来的区域和外界完全隔开水才真正被困住。1.2 边界连通性决定能否蓄水的唯一标准为了把问题讲清楚先定义一个概念每个格子的水面高度w[i][j]表示下雨后该格子上方水面最终到达的海拔。那么答案就是所有w[i][j] - a[i][j]的和积水和地面高度本身没关系只和“水面比地面高多少”有关系。现在关键变成w[i][j]到底怎么求用一个很直观的视角来看。假设你站在某个格子上想判断水位能不能涨到 h。如果这个格子和边界之间存在一条路径路径上所有格子的高度都不超过 h那么水面一旦涨到 h水就会顺着这条通道流出去所以最终水位必然低于 h。反过来如果所有能走到边界的路径上都至少有一座高于 h 的“墙”挡着那么水涨到 h 就会被拦住一直积累到 h 再漫过墙。把这句话翻译成图论语言w[i][j]等于从该格子到任意边界格子的所有路径中“路径上最大海拔”的最小值。也就是图论里的最小瓶颈路径问题。这个定义特别重要后面所有算法本质上都在求这个结果。理解了“边界连通性”这个核心概念就能明白为什么最外圈永远不积水边界格子本身就是墙它们的高度不参与积水。而且向外流出的通道长度为 0w[i][j]直接等于自身高度积水为 0。2. 先热身一维接雨水的单调栈与双指针2.1 单调栈的结算时机虽然二维不能直接套一维模板但一维的单调栈思路值得先复习一遍因为后面理解“有效水面高度”会用到。一维接雨水里单调栈维护的是一个高度递减的下标序列。从头遍历每个柱子当遇到当前高度大于栈顶高度时说明栈顶位置可能形成了一个凹槽的“坑底”。此时弹出栈顶记作 bottom如果栈为空就直接丢掉因为左边没有墙。如果栈不为空新的栈顶 left 就是左侧墙当前遍历到的 i 就是右侧墙。宽度是i - left - 1高度是min(h[i], h[left]) - h[bottom]两者相乘就是这一段凹槽的水量。long long trap1D(const vectorint h) { stackint st; // 栈里存下标 long long ans 0; for (int i 0; i (int)h.size(); i) { while (!st.empty() h[i] h[st.top()]) { int bottom st.top(); st.pop(); if (st.empty()) break; // 左边没有墙存不住水 int left st.top(); int width i - left - 1; int height min(h[i], h[left]) - h[bottom]; ans 1LL * width * height; } st.push(i); } return ans; }这个模板要背牢但要特别注意它结算的是“坑底”不是“柱子本身”。弹出 bottom 时bottom 是被左右墙夹住的最低点水一定是先填充这里。这种“从底到顶逐段结算”的想法其实和二维问题里按高度层灌水是类似的。2.2 双指针为什么扩展不到二维一维还有一种 O(n) 双指针写法左右两个指针向中间靠拢每次移动高度较低的一侧同时维护两侧最大值。它之所以成立是因为一维的水位只由左右两侧最大值决定中间没有岔路。二维里能不能也搞两个指针不行。二维的“边界”是一整圈不是一个点。一个内部格子的水可能从东边流出去也可能从北边、南边、西边流出去根本不是左右两堵墙能描述的。硬套双指针唯一的结局就是样例都过不了。2.3 思维转场从“左右夹逼”到“整体扩散”一维的核心是“找每个位置两侧最大高度的较小值”。二维的核心换成“找每个位置到边界最小瓶颈路径的瓶颈值”。这两个表述差得很远但有一个共同点都是从小到大找“最低的约束”。一维里最低的约束是min(左墙, 右墙)。二维里最低的约束是“到边界路径上的最大高度最小值”。能不能用某种方式让水从边界开始一层一层向里扩散每次扩散都走当前最低的“缺口”这就是下一章优先队列算法的朴素想法。3. 核心算法优先队列BFS水从最低缺口漫进来3.1 小根堆里存的不是地形高度而是有效水面高度二维接雨水最经典的解法是“边界灌水法”。把所有边界格子加入一个小根堆堆顶始终是当前所有“已知边界”里高度最小的那个。每次从堆顶取出格子 cur检查它上下左右四个方向的邻居。如果邻居没有访问过分两种情况处理邻居高度a[nx][ny] cur.h说明邻居比当前格子低水会从 cur 这个缺口漫过去把这个邻居淹没到cur.h的高度。积水量增加cur.h - a[nx][ny]然后把这个邻居也放入堆中但它在堆里记录的高度应该是cur.h而不是它自己的地形高度。邻居高度a[nx][ny] cur.h说明邻居本身是一堵更高的墙水漫不过去。这个邻居不会积水直接以它自身高度入堆即可。这里就是最容易绕晕的地方堆里存的高度不是地形高度而是“如果这个格子被淹没水面会停在多高”的有效高度。为什么因为一个低洼格子被淹没后它不再是一块凸起的陆地而是变成了水域的一部分。这片水域的水面海拔就是cur.h。当继续向内扩展时这片水域是整体作为一个“边界”存在的所以要用cur.h继续去约束更内部的区域。生活化理解拿一个底部有洞的盆接水水总是先从最低的洞漏出去。这里的小根堆就是不断找出“当前最低的洞”水从那里向盆地内部蔓延。如果某个邻居比洞口还矮它就会被水淹没如果邻居比洞口高它就是一个新的挡水墙。3.2 完整C实现与代码逐段解释#include bits/stdc.h using namespace std; struct Cell { int h, x, y; bool operator(const Cell other) const { return h other.h; // 让 priority_queue 变成小根堆 } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; if (!(cin n m)) return 0; vectorvectorint a(n, vectorint(m)); for (int i 0; i n; i) for (int j 0; j m; j) cin a[i][j]; vectorvectorint vis(n, vectorint(m, 0)); priority_queueCell pq; // 所有边界格子入堆初始高度就是自身地形高度 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) { vis[i][j] 1; pq.push({a[i][j], i, j}); } } } long long ans 0; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; while (!pq.empty()) { Cell 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 || vis[nx][ny]) continue; vis[nx][ny] 1; if (a[nx][ny] cur.h) { ans cur.h - a[nx][ny]; pq.push({cur.h, nx, ny}); } else { pq.push({a[nx][ny], nx, ny}); } } } cout ans \n; return 0; }代码本身并不长核心逻辑只体现在几行。这里强调两个实现细节。第一个细节Cell 的比较运算符必须反向重载。priority_queue默认是大根堆最大的元素在堆顶。我们希望每次取最小的h所以operator内部写成return h other.h;。新手容易写反一写反整个算法就变成从最高的墙开始灌水结果完全错误。第二个细节外圈入堆的高度必须是自身高度。边界格子如果本身是低洼的比如一个 0 高度的边界格子它入堆高度就是 0。后续弹出的顺序会从最低的开始完全符合水往低处流的物理规律。3.3 复杂度分析与模板记忆要点这个算法每个格子最多入堆一次每次入堆和弹出都是 O(log(nm))所以总复杂度是 O(nm log(nm))空间复杂度 O(nm)。不管你 n、m 是几百还是几千这个复杂度都完全够用是目前二维接雨水最主流的做法。我把这套模板记忆要点总结为三句话边界先入堆高度用自身弹出找缺口邻居水漫过邻居若更低水位取堆顶。写熟练之后这题从读题到 AC 一般不会超过二十分钟。相比调试时各种玄学错误先理解“堆里存的是有效水面高度”这个原则更重要。4. 另一条路分层灌水、并查集与二维前缀和的配合4.1 按高度层暴力灌水适合写对拍优先队列解法是考场上的正解但我在实际做题时还写过另一种非常直观的暴力分层法用来验证答案。思路是把降水过程想象成一层一层叠加。假设最大高度是 maxh从 h 1 到 maxh 枚举每一层。对于当前层 h从所有边界格子出发沿着高度小于 h 的格子做 BFS能走到的都标记为“可流出”。所有高度小于 h 且没有被标记的格子就是被高墙围住、在高度 h 这一层存住了水的格子。每层统计一次累加这些格子的数量最终就是总体积。long long layerBrute(const vectorvectorint a, int n, int m) { int maxh 0; for (int i 0; i n; i) for (int j 0; j m; j) maxh max(maxh, a[i][j]); long long ans 0; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; for (int h 1; h maxh; h) { vectorvectorint mark(n, vectorint(m, 0)); queuepairint, int q; 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) a[i][j] h) { mark[i][j] 1; q.push({i, j}); } } } while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (int d 0; d 4; d) { int nx x dx[d], ny y dy[d]; if (nx 0 || nx n || ny 0 || ny m) continue; if (mark[nx][ny] || a[nx][ny] h) continue; mark[nx][ny] 1; q.push({nx, ny}); } } int cnt 0; for (int i 0; i n; i) for (int j 0; j m; j) if (a[i][j] h !mark[i][j]) cnt; ans cnt; } return ans; }这段代码的复杂度是 O(maxh * n * m)数据小的时候完全能干而且思路和“水位逐步上升”的物理过程完全一致。我强烈建议写完正解后保留这个暴力函数用来随机生成小数据对拍。4.2 二维前缀和能帮什么忙不能帮什么忙热搜词里有“信奥前缀和公式”那就顺带讲一下二维前缀和在这个题目里的位置。二维前缀和的核心公式是sum(x1, y1, x2, y2) s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] s[x1 - 1][y1 - 1]它能在 O(1) 时间内求出任意矩形区域内格子的高度总和、格子数量等统计量。在这个题目里二维前缀和能做到的是如果我们已经知道某个矩形区域的蓄水范围可以快速算出这个区域里地面高度总和从而得到积水量。但问题是蓄水区域往往是不规则连通块不是矩形二维前缀和不是万能的。真正不能说谎的结论是前缀和在这个题目里是辅助工具不是核心解法。核心难点仍然是判断哪些区域与边界连通这必须靠 BFS、堆或并查集。考场上如果看到“统计矩形区域和”的需求才优先想前缀和。4.3 三种思路选型对比我把三种解法放在一起对比方便大家按场景选择方法时间复杂度代码难度适用场景优先队列 BFSO(nm log(nm))中等考场首选通用性强按高度层暴力 BFSO(maxh * nm)低数据小、写对拍并查集按高度合并O(nm log nm)较难高度离散值多、追求更低复杂度优先队列法代码量不大而且正确性高是我在主考场景下的唯一推荐。并查集思路适合学有余力时理解但不建议在正式比赛里临时写因为合并方向、边界判断这些细节一旦出错很难查。暴力法虽然复杂度高但胜在逻辑简单绝对是调试时最可靠的对照物。5. 实战踩坑与调试实录5.1 边界初始高度填 0样例直接崩我第一次写的时候惯性思维把边界所有格子都当作水位 0 入堆觉得“边界不积水水位就是 0”。结果样例都过不了算出来的答案比正确答案大很多。原因很简单边界格子自身地形高度不是 0。比如左下角是一个高度为 5 的格子它虽然不积水但它作为墙可以拦住内部水位最高到 5。如果你把它当成水位 0 入堆内部低洼区域就会被错误地判定为“水会从高度 0 的缺口流走”实际根本流不走。入堆初值必须用边界格子自身的地形高度这个细节决定了整体算法的正确性。5.2 入堆时就要标记访问不要等到弹出这是我调试时踩的第二个坑。刚开始我在弹出堆顶时才标记访问导致同一个邻居被多个不同方向的格子反复入堆。虽然小根堆最终弹出的仍是较小的高度答案不一定错但复杂度会退化而且调试时数据一大就很混乱。正确做法是在把邻居压入堆的那一刻就标记成已访问。因为每个格子的最优水面高度只可能被更新一次先到先得入堆时标记可以保证每个格子只入堆一次。这个习惯在很多图论题里都通用提前标记不仅能防止重复计算还能减少不必要的堆操作。5.3 特殊场景全等高度、单行单列、零高度边界情况往往暴露问题。比如 3x3 的全 0 矩阵答案应该是 0。算法里边界入堆高度都是 0弹出后邻居高度也不小于 0没有积水正确。比如 1x5 的一列数据所有格子都是边界输出 0也正确。看起来最安全的往往最容易出错写完之后至少跑一遍这类小用例再提交。高度为 0 的格子特别需要注意。一个内部高度为 0 的格子被高度为 3 的墙围着它最终能蓄 3 格水。但如果你在 BFS 时只考虑“高度小于 cur.h 才积水”0 是小于 3 的所以能正确累加。这个没有问题。真正的问题是边界入堆初值不要被“0”干扰边界格子即使地形为 0那也是它作为墙的真实高度。5.4 随机对拍在比赛里救命的十分钟单独写一个算法再对很难发现隐藏 bug所以我强烈建议对拍。步骤很简单写一个数据生成器随机生成 n、m 和每个格子的高度n、m 控制在 5 以内高度在 0 到 5 之间跑一遍正解程序再跑一遍暴力分层程序比较两个输出不一样就输出这组数据。我实际对拍时抓到过不少问题其中最有价值的是当边界某个格子高度很大时我错误地把所有边界格子统一初始化为 0导致答案偏大。这种极端数据构造起来很简单但一开始根本不会想到。对拍十分钟换来的是一整天的安心非常划算。5.5 个人刷题体会这个模型还能迁移到哪些题刷完这题之后我的最大感受是它表面是“接雨水”内核却是图论里的最小瓶颈路径。只要能识别出“从某个点到边界的最低瓶颈”优先队列BFS 的模板就能直接套。类似的题还有 LeetCode 407 二维接雨水、一些以“水位上涨”为背景的连通性题目都是同一个模型。我个人的习惯是把这类题的模板单独存一个文件夹注释里写上“堆中存有效水面高度”和“入堆即标记”两条原则比赛前翻一遍。即使题目换个马甲变成“洪水淹没城市”“被水围住的岛屿”只要它让你计算被水淹没的体积你都能第一时间反应出这套解法。信奥做题到后期比的不是背了多少题而是能不能把一类问题背后的图论模型看穿这一题就是很好的训练样例。