水洼个数：DFS、BFS与并查集三种解法详解

水洼个数，一道练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 数组，长度为 M+1 预留一个终止符位置。

再一个容易疏忽的是边界判断。比如第一行的格子往上走就越界了，最后一列的格子往右走就越界了。如果你用 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) { queue<pair<int, 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[im+j] == im+j，在某些合并路径后可能不是根的格子也有这种巧合，所以更稳妥的是统一调用 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 三种方法复杂度对比

我把三种方法的维度整理成一个表，方便你从复杂度到代码量做对比：

这里 α 是反阿克曼函数，可以近似认为是一个极小的常数，所以并查集的时间复杂度在实际应用中也是线性的。你不需要背这个函数，只要知道并查集跑起来很快就行。

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(im+j) == im+j 判断根节点，不要直接用 fa[im+j] == im+j。因为路径压缩后，有些节点的 fa 指向的是根节点的父级链上的中间节点，直接比较可能误判。如果你已经确保每次操作后都做了完整路径压缩，直接比较也没问题，但统一用 find 更稳妥，代码也更好阅读。

6.5 常见错误速查表

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 2386（Lake Counting），它就是这道题的英文原题；LeetCode 200 岛屿数量可以练四方向版本；LeetCode 695 岛屿的最大面积可以练连通块大小统计。这几道题由简到难，覆盖了连通块问题的核心套路，刷完建立一个统一的“网格连通块解题模板”，以后再遇到类似题目基本就能秒杀。

写在最后

水洼个数这道题，代码量不大，但考察的点非常集中：方向控制、边界处理、搜索顺序、数据规模分析，这四样东西在几乎所有搜索题里都会遇到。我个人在实际操作中的体会是，不要满足于写出一种解法就交卷，花半小时把 DFS、BFS、并查集三个版本都写一遍，收获绝对比刷十道类似的新题大得多。最后再分享一个小技巧：无论用哪种解法，先在本地造几个极端测试数据跑一遍，一个是全 W 的网格，一个是全 . 的网格，还有一个是只有单独一个 W 的网格，这三个数据几乎能验证掉你代码里百分之八十的潜在问题。