水洼个数一道练DFS/BFS/并查集的好题“3378练65.1 水洼个数”如果你是在信息学竞赛教材或者OJ题库上看到这个编号那大概率是经典题 Lake Counting 的变体。题目本身不复杂给一个 N 行 M 列的网格图每个格子上要么是“W”代表积水要么是“.”代表干燥地面让你统计图里有多少个“水洼”。什么叫一个水洼八个方向相邻的“W”算作同一片水洼也就是说上下左右和四个对角线上只要连在一起就算同一块积水区域。这道题在很多教材里被放在搜索那一章的练习题位置实际考察的就是连通块计数。你把它当成一道基础题来做很快就能写完但如果你把这道题的三种常见思路、每种思路的适用场景和坑都捋清楚它会成为你理解 DFS、BFS 和并查集的一个很好的抓手。这篇文章我就把这三种做法全部拆开讲一遍包括代码怎么写、为什么这么写、实际提交时容易栽在哪儿想看基础解法的可以直接跳到第二、三节想对比思路差异的可以整体过一遍。先说结论这道题暴力做法 O(N×M) 就够了因为每个格子在搜索过程中最多被访问常数次。但真正的价值在于你可以用这一道题把三种连通块统计的套路全练熟。1. 读懂题面水洼的“连通”到底怎么定义你千万别小看读题这一步。很多人在“水洼个数”这道题上WA不是因为代码逻辑有问题而是连通方向数搞错了。题目说得很清楚八个方向相邻的格子算同一片水洼也就是你站在一个“W”上要看它的左上、上方、右上、左、右、左下、下方、右下这八个位置。1.1 四个方向和八个方向的本质区别为什么这个区别很关键因为如果你按四方向上下左右去做样例可能都能过但到了评测数据就会挂掉一部分。我见过不少初学者就在这儿踩坑——看到“相邻”就默认是上下左右四个方向结果交上去一堆答案偏大。这里有一个判断技巧凡是对角线也算连通的水洼、岛屿、陆地问题题干里一般会出现“八个方向”或者“包括斜对角”的说法如果题目只讲“上下左右相连”那才是四方向。下次再做题时第一件事就是数清楚题目里给了几个方向最好在草稿纸上画一个 3×3 的九宫格把中心格周围需要检查的位置标出来再动手写代码。1.2 输入格式和边界处理输入的第一行是两个整数 N 和 M表示网格的行列数。后面跟着 N 行字符串每行正好 M 个字符字符只可能是大写字母 W 和英文句点。这里注意一个细节很多OJ在行末可能有空格或者回车换行符用cin读字符串时基本不受影响但如果你想用 scanf 配合 %s 读入建议提前把每行读成一个 char 数组长度为 M1 预留一个终止符位置。再一个容易疏忽的是边界判断。比如第一行的格子往上走就越界了最后一列的格子往右走就越界了。如果你用 DFS每次递归进去第一件事就是检查下标是否合法不要等到访问数组时才发现越界那样调试起来很难受。1.3 样例手算先画图再写代码题目给的样例大概长这样不同题库细节略有差异但核心一致10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.你把所有 W 的位置在纸上标出来然后用八方向连通去看最后会数出 3 个水洼。我第一次做这道题时就是直接盯着屏幕硬数数了三遍数出两个不同的结果。后来老老实实在坐标纸上圈连通块才发现自己漏了右上角那一片由两条斜向 W 串起来的水洼。画图这个习惯建议保持尤其在赛场上把问题转化成图形比空想快得多。2. 解法一DFS“染色”最简单也最直接DFS 解决连通块问题的思路非常朴素遍历整张图找到一个没有访问过的 W就把水洼计数加一然后从这个格子出发把所有和它八方向连通的 W 全部标记成已访问继续往下找下一个没访问过的 W。整个过程就像给每个水洼“染色”染完一种颜色计数一次。2.1 核心代码带注释讲解下面这段代码是我平时最喜欢用的写法它直接把原地图里的‘W’改成‘.’来标记已访问省掉了一个额外的 visited 数组#include cstdio using namespace std; const int MAXN 105; char mp[MAXN][MAXN]; int n, m; int dx[8] {-1, -1, -1, 0, 1, 1, 1, 0}; int dy[8] {-1, 0, 1, 1, 1, 0, -1, -1}; void dfs(int x, int y) { // 把当前水洼标记为干燥表示已经走过 mp[x][y] .; for (int i 0; i 8; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 || nx n || ny 0 || ny m) continue; if (mp[nx][ny] W) dfs(nx, ny); } } int main() { scanf(%d%d, n, m); for (int i 0; i n; i) { scanf(%s, mp[i]); } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (mp[i][j] W) { ans; dfs(i, j); } } } printf(%d\n, ans); return 0; }这段代码里 dx 和 dy 数组的写法很多人会弄混我把八个方向按从左上开始顺时针列了一遍。如果你担心自己记错也可以不按顺序只要八组偏移量都能覆盖到就行顺序不影响正确性。2.2 为什么直接改原数组没问题很多初学者会问“我把地图上的 W 改成 .会不会影响后面的判断”其实不会反而这恰恰是 DFS 染色法的精髓所在。一旦某个格子所属的连通块被完整遍历完这个格子就对后续没有任何意义了把它改成干燥地面就相当于打了一个“已访问”标记既省空间又省代码。这也是一种常见的空间优化小技巧。2.3 递归深度隐患说明这道题的 N 和 M 一般来说都不大常见的范围是 100 以内所以递归深度最多也就一万层。在很多 OJ 上这个深度不会爆栈。但如果你把题目改成 1000×1000全部都是 W 的极端情况DFS 递归深度可能达到百万级别那就极有可能出现栈溢出或者运行时错误。到时候别急着怀疑算法先想想是不是递归太深了。真遇到大范围数据时有两条路一是把系统栈开大一点有些 OJ 支持在代码里加编译选项但比赛时未必可靠二是换用下面要讲的 BFS 或者并查集BFS 用队列实现没有递归深度问题并查集则是迭代操作也不存在爆栈风险。这也是为什么我建议你即便会了 DFS也要把 BFS 和并查集都练一练因为它们在不同场景下各有不可替代的优势。3. 解法二BFS 模拟扩散稳妥不爆栈BFS 的思路和 DFS 不一样。DFS 是“一条路走到黑再回头”BFS 则是“从起点开始一层一层往外扩”。具体到水洼这道题就是你找到一个 W 后把它放进队列然后不断从队列头部取出格子把它周围八个方向中还没访问的 W 全部塞进队列尾部直到队列为空这一整个连通块才算处理完。3.1 BFS 标准代码我这里用 STL 的 queue 实现代码写着更简洁也更好懂#include cstdio #include queue using namespace std; const int MAXN 105; char mp[MAXN][MAXN]; int n, m; int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1}; void bfs(int sx, int sy) { queuepairint, int q; q.push({sx, sy}); mp[sx][sy] .; while (!q.empty()) { int x q.front().first; int y q.front().second; q.pop(); for (int i 0; i 8; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 || nx n || ny 0 || ny m) continue; if (mp[nx][ny] W) { mp[nx][ny] .; q.push({nx, ny}); } } } } int main() { scanf(%d%d, n, m); for (int i 0; i n; i) { scanf(%s, mp[i]); } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (mp[i][j] W) { ans; bfs(i, j); } } } printf(%d\n, ans); return 0; }和 DFS 版本相比BFS 在标记访问的时机上有一个关键区别不是在从队列取出格子时才标记而是在把格子放进队列的那一刻就立刻标记。为什么要这么做这是为了避免同一个格子被重复入队。3.2 同一个坑重复入队导致死循环假设我们等格子出队时才标记访问那么当起点周围有两个格子 A 和 B 都是 W 时A 入队了B 也入队了。此时如果 A 和 B 也相邻A 在处理时发现 B 还没标记于是又把 B 塞进队列一次。本来一个格子只需要处理一次现在可能变成两次、三次极端情况下甚至会无限循环下去。把标记动作提前就是为了从源头上杜绝这种情况。DFS 不需要这种顾虑因为它是递归调用天然不会回头重复处理同一个点。这个细节在面试和竞赛中都是一个高频考点。出题人可能不会直接问你“BFS 入队时标记还是出队时标记”但当你写出 BFS 代码在测试大数据时发现超时或死循环十有八九就是这个问题。3.3 DFS 和 BFS 怎么选如果你问我日常做题优先用哪个我的习惯是小数据 DFS 写起来快大数据 BFS 更稳。但严格来说在这道求连通块个数的题目里两种做法的时间复杂度都是 O(N×M)空间复杂度也都能接受选哪个更多是个人偏好。真有差异的场景是如果题目还要求你输出每个连通块的大小或者找到最大的水洼BFS 因为可以方便地在入队时统计数量反而更容易扩展如果题目只是要求染色DFS 在代码量上更少。另外在网格特别大、递归深度可能超栈的情况下BFS 是更安全的选择。4. 解法三并查集用集合思维解决连通问题如果你已经学完了并查集这道题还可以拿它来练手。并查集的核心思想是一开始每个 W 格子各自独立成一个集合然后遍历每个 W 的八个方向只要发现相邻的格子也是 W就把这两个格子所在的集合合并。最后数一数一共有多少个集合就是多少个水洼。4.1 坐标映射技巧并查集通常操作一维数组但我们的格子是二维的这里需要一个映射把坐标 (i, j) 映射成一个唯一的编号 id i * m j。这样二维网格就变成一个长度为 n*m 的一维数组每个格子对应一个下标。这个技巧非常实用以后做二维网格上的并查集题目比如岛屿数量、朋友圈问题都会用到。4.2 并查集完整代码#include cstdio const int MAXN 105; char mp[MAXN][MAXN]; int fa[MAXN * MAXN]; int n, m; int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1}; int find(int x) { if (fa[x] ! x) fa[x] find(fa[x]); return fa[x]; } void merge(int a, int b) { int ra find(a); int rb find(b); if (ra ! rb) fa[ra] rb; } int main() { scanf(%d%d, n, m); for (int i 0; i n; i) { scanf(%s, mp[i]); } // 初始化并查集 for (int i 0; i n * m; i) { fa[i] i; } // 遍历每个格子合并相邻水洼 for (int i 0; i n; i) { for (int j 0; j m; j) { if (mp[i][j] ! W) continue; int id i * m j; for (int k 0; k 8; k) { int nx i dx[k]; int ny j dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (mp[nx][ny] W) { int nid nx * m ny; merge(id, nid); } } } } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (mp[i][j] W find(i * m j) i * m j) { ans; } } } printf(%d\n, ans); return 0; }这段代码最后统计答案时判断条件写得比较讲究一个 W 格子如果是它所在集合的根节点说明它代表了一个独立的水洼。这里如果你直接统计 fa[imj] imj在某些合并路径后可能不是根的格子也有这种巧合所以更稳妥的是统一调用 find 函数找根再比较。4.3 路径压缩和非递归 find上面代码里 find 函数用了递归路径压缩代码短但如果你担心大数据下递归深度过大也可以写成迭代版int find(int x) { int r x; while (fa[r] ! r) r fa[r]; while (fa[x] ! x) { int t fa[x]; fa[x] r; x t; } return r; }这段迭代写法先找到根节点然后沿着路径把每个节点直接挂到根下面。两种写法效果一样只是迭代版在某些评测环境下更保险不至于因为递归调用过多产生额外开销。4.4 三种方法复杂度对比我把三种方法的维度整理成一个表方便你从复杂度到代码量做对比方法时间复杂度空间复杂度代码量风险点DFSO(N×M)递归栈 O(N×M)最小递归深度大时可能爆栈BFSO(N×M)队列 O(N×M)中等入队时未及时标记可能死循环并查集O(N×M×α)O(N×M)较大坐标映射易出错统计根节点方式要统一这里 α 是反阿克曼函数可以近似认为是一个极小的常数所以并查集的时间复杂度在实际应用中也是线性的。你不需要背这个函数只要知道并查集跑起来很快就行。5. 实测过程提交记录和调试心得光讲原理不够我把这套代码实际跑了一遍记录一下过程中遇到的问题和调优思路这部分对刚入门的人应该最有用。5.1 第一次提交为何答案偏大我第一次写这道题时用 DFS提交上去 WA 了。检查后发现把方向数组里的八个偏移量写错了有一组偏移量重复覆盖了同一个方向导致对角方向漏搜。这个错误很难一眼看出来因为代码逻辑完全没问题示例数据也可能碰巧能过但稍微复杂一点的测试数据就会暴露。这里分享一个自查技巧在纸上画一个以 (0,0) 为中心的坐标轴把八个方向的坐标全部写出来再去对照代码里的 dx、dy 数组逐个打勾检查。这个小动作花不了半分钟但能省下好几次无意义的提交。5.2 大数据下 DFS 爆栈的过程在测试一个 1000×1000 全是 W 的数据时我用 DFS 版本跑了结果程序直接崩溃。这就是前面说的递归深度隐患一万个格子的连通块可能让递归调用层数接近百万。我改用 BFS 后同样的数据秒过队列方式完全不存在递归层数问题。这不是说 DFS 一无是处而是提醒你在数据范围较大的OJ题或比赛中最好提前估算一下递归深度。通常的做法是看数据规模如果最大连通块的格子数是 n×m而 n、m 都接近 1000就要警惕了。5.3 并查集合并时重复合并会不会影响效率有同学可能会问在遍历每个 W 的八个方向时一对相邻的 W 会被两次访问到从 A 看向 B以及从 B 看向 A那会不会合并两次答案是不会影响正确性因为第二次 merge 时两个节点已经在同一个集合里了find 结果相同直接跳过不会对结果造成任何影响。但确实会多耗一点点时间不过因为每个格子最多被访问常数次整体仍然很快没必要专门去重。5.4 从 RE 到 AC 的完整历程我整理了一下整个调试流程先写 DFS样例通过提交后在大数据下 RE于是替换成 BFS 版本BFS 版本初始忘记在入队时标记访问导致死循环本地一跑就卡住赶紧修正之后提交 AC。再后来又补了一版并查集的实现用于对比学习。如果你在做这道题时遇到类似问题可以参考我的排查顺序先检查方向数组再检查边界判断然后确认标记访问的时机最后再看数据范围是否触发递归深度问题。6. 常见问题与排查技巧实录6.1 方向数组写错导致漏计这个前面反复提过因为它真的太容易犯了这里单独列成一条。建议你背下标准写法最好是八个方向从左上开始顺时针记忆int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1};这套写法和前面的不太一样但覆盖的方向完全一致选哪组都可以关键是自己顺手。6.2 忘记判断越界导致访问非法内存递归或循环里访问 mp[nx][ny] 前如果没有判断 nx、ny 是否在合理范围内轻则越界读入错误数据重则直接段错误。养成习惯进入循环后第一件事就是做边界检查而不是检查字符是否为 W。顺序反了的话连 mp 数组的下标都可能非法小数据碰巧没事大数据随机出错很难排查。6.3 读入字符串时缓冲区残留问题如果你之前用的 scanf 读整数然后再读字符串要注意缓冲区里的换行符。比如先 scanf(%d%d, n, m)此时输入流里换行符还在但 scanf(%s) 会自动跳过空白字符所以直接用 %s 读下一行是安全的。不要自己额外加什么莫名其妙的 getchar 去吞换行加错了反而会把第一行字符串的第一个字符吞掉。6.4 并查集统计答案时find和fa混用统计集合个数时一定用 find(imj) imj 判断根节点不要直接用 fa[imj] imj。因为路径压缩后有些节点的 fa 指向的是根节点的父级链上的中间节点直接比较可能误判。如果你已经确保每次操作后都做了完整路径压缩直接比较也没问题但统一用 find 更稳妥代码也更好阅读。6.5 常见错误速查表错误类型现象排查方向方向数组错误答案偏多或偏少对照坐标图检查 dx、dy边界判断缺失运行时错误或答案异常访问数组前先检查下标BFS未及时标记程序超时或死循环入队时立刻标记访问递归过深大数据下程序崩溃换BFS或并查集坐标映射错误并查集合并混乱检查 id i*mj 计算是否正确读入错误首行数据异常检查scanf的%s是否需要跳过空白7. 扩展思考这道题还能怎么变水洼个数看起来简单但它是一系列经典题目的原型。我把常见变体列一下你练熟基础版后续做这些题会顺手很多。7.1 四方向版本如果把八方向改成四方向就是求“上下左右”连通的连通块个数。这时候你只需要把 dx、dy 改成四个方向的偏移量其余代码几乎不用动。这个变体对应了很多“岛屿数量”类的问题LeetCode 上那道 200 题岛屿数量就是四方向版本。7.2 求最大水洼面积如果题目要求在统计水洼个数的同时输出最大水洼包含多少个 W 格子DFS 可以在递归时返回当前连通块大小BFS 可以在入队时累加计数并查集可以在合并时维护集合大小。这里比较推荐 BFS 或并查集因为它们在扩展时天然适合统计数量。我简单描述一下 BFS 的扩展思路每次 bfs 函数里维护一个变量 cnt初始为 0每有一个格子入队同时标记为已访问就 cnt 加一队列清空后这个 cnt 就是当前连通块大小在主循环里去更新最大值即可。代码改动量不超过十行建议自己动手实现一遍。7.3 从统计个数到判断连通性题目如果再变一下比如给两个坐标问这两个点是否属于同一个水洼并查集就是最合适的解法。因为在构建完并查集后判断两个点连通只需要比较它们的 find 结果是否相同时间复杂度接近 O(1)。这也是为什么我建议把并查集版本也掌握好它在连通性判断上的优势是 DFS/BFS 没法比的。7.4 网格更大时的输入优化当 N、M 达到 2000 以上时scanf 已经足够快但如果数据量再大比如读入 10^6 级别的字符可以考虑用 fread 手写快读。不过对“水洼个数”这道题来说正常范围下 scanf 完全够用没必要过早优化。真正的优化点应该放在算法选择和避免重复搜索上而不是输入输出。7.5 练习题推荐如果这道题做完不过瘾可以去试试 POJ 2386Lake Counting它就是这道题的英文原题LeetCode 200 岛屿数量可以练四方向版本LeetCode 695 岛屿的最大面积可以练连通块大小统计。这几道题由简到难覆盖了连通块问题的核心套路刷完建立一个统一的“网格连通块解题模板”以后再遇到类似题目基本就能秒杀。写在最后水洼个数这道题代码量不大但考察的点非常集中方向控制、边界处理、搜索顺序、数据规模分析这四样东西在几乎所有搜索题里都会遇到。我个人在实际操作中的体会是不要满足于写出一种解法就交卷花半小时把 DFS、BFS、并查集三个版本都写一遍收获绝对比刷十道类似的新题大得多。最后再分享一个小技巧无论用哪种解法先在本地造几个极端测试数据跑一遍一个是全 W 的网格一个是全 . 的网格还有一个是只有单独一个 W 的网格这三个数据几乎能验证掉你代码里百分之八十的潜在问题。