东方博宜OJ 1435 这道「数池塘八方向」是 Flood fill 入门题单里很有代表性的一道。第一次看到它的时候我想这不就是往地图上撒种子、把连在一起的水域数一遍吗结果第一版代码交上去直接 WA后面排查才发现是方向数组里漏了一个对角线。后来把这道题彻底吃透才真正理解连通块计数这一整类题目的套路也顺带把 DFS、BFS、并查集三种思路在同一道题上打通了。这篇文章我会给出完整可提交的代码把「数池塘」从读题建模、Flood fill 原理、三种实现方案到评测翻车点和实战迁移一次讲清楚。无论你是刚学到 DFS 的新人还是想系统复习连通块题型的选手都能从这里拿到可以直接照抄的模板以及一些常规题解里不会写的经验。1. 先读透题意八方向连通到底意味着什么1.1 题面约定与一个手算示例这道题的题干在不同 OJ 平台上措辞略有差异但核心约定保持了一致输入第一行是两个整数 N 和 M表示地图有 N 行 M 列紧接着是 N 行字符串每行长度恰好为 M。字符W表示水.表示干地。输出是一个整数表示地图中池塘的总数量。很多初学者容易忽略一个点地图是一行字符串整体给你的不是逐个字符用空格隔开的。这意味着读入时按行读字符串、再逐字符填入二维数组是最稳的做法后面我会专门说输入读取的坑。用手算一个小例子感受一下输入4 6 W.W..W .WW... ..WW.. ......先把每个W的坐标列出来第 0 行(0,0)、(0,2)、(0,5)第 1 行(1,1)、(1,2)第 2 行(2,2)、(2,3)按八方向连通规则(0,0) 和 (1,1) 是左下右上的对角线关系属于相邻(1,1) 又和 (0,2)、(1,2)、(2,2) 相连而 (2,2) 和 (2,3) 左右相连。这一整块 6 个W全部属于同一个池塘。剩下 (0,5) 孤零零的上下左右和四条对角线方向全都不是W所以它是第二个池塘。最终答案输出 2。1.2 把字符网格翻译成一张图做过图论题的人看到这道题通常会会心一笑这本质上就是数连通分量。把每个格子看成图的一个节点但只有内容为W的格子才可能成为池塘的一员。两个W格子之间只要满足八方向相邻就认为它们之间存在一条边。题目要求的池塘数量就是这张图里所有极大连通集合的数量。为什么要做这层抽象因为一旦想清楚节点 边 连通分量这个结构解题方案就变得非常清晰要么从一个W出发把整个连通块遍历一遍并打上访问标记然后换下一个没被访问的W继续要么把所有相邻的W合并到同一个集合里最后统计有多少个集合。这两条路分别对应 DFS/BFS 和并查集都是这套抽象的自然产物。1.3 四方向改成八方向答案可能差多少很多人以为八方向就是把上下左右改成上下左右加四个对角代码多写四行而已。但真正需要注意的是对角线连通会显著增加连通块合并的概率。看一个最简单的对比地图是 2 行 2 列W. .W如果按四方向判断(0,0) 和 (1,1) 只有对角线关系不算相邻答案是 2 个池塘。但按题目要求的八方向判断(0,0) 通过左下方向直接连到 (1,1)答案变成 1。同一个地图两种连通规则答案完全不同。这就是为什么下手写代码之前先确定题目到底要哪种连通性比什么都重要。方向数组不是顺便支持一下的功能而是直接决定答案正确性的核心参数。2. Flood fill 原理凭什么能一个不落数完所有池塘2.1 油漆桶模型与递归扩散Flood fill 中文叫泛洪填充。如果你用过画图软件里的油漆桶工具其实早就见过它了点在一个封闭区域里颜色就沿着相邻像素不断往外扩散直到碰到边界才停下。这道题的 DFS 做法就是把油漆桶搬到了字符网格上。具体来说主函数从地图左上角开始扫描遇到第一个没被访问过的W时把它当作一个池塘的种子然后从这个格子出发向八个方向递归扩散。扩散的规则是只要邻居还是W且没被访问过就走过去继续扩散。当一次扩散结束时这个池塘里所有W就都被染过色了池塘计数加一。接着主函数继续扫描找下一个没染色的W再重复整个过程。这个过程之所以能保证一个不落、一个不多靠的是两层保证外层扫描保证每个W都会被作为种子尝试一次内层扩散配合访问标记保证每个W只属于一个连通块。两者缺一不可。2.2 标记数组是整个算法的灵魂很多第一次写 Flood fill 的人会在标记这个环节翻车。标记数组vis至少承担两个职责防止递归/循环在两个格子之间无限往返。如果不标记(0,0)走到(1,1)(1,1)又走回(0,0)程序就死循环了。让外层主循环知道哪些格子已经被归入某个池塘避免重复计数。还有一种替代方案是直接修改原图把访问过的W改成.。这样连vis数组都省了代价是破坏了原始数据。在 OJ 题上无所谓但在真实项目里如果后面还要用原图就要慎重。关于复杂度每个格子最多被访问一次每次访问固定检查 8 个方向所以总复杂度是 O(N×M) 量级对这道题的数据范围来说非常充裕。这也是 Flood fill 这类全图遍历染色算法最吸引人的地方思路直接效率也不用担心。2.3 DFS、BFS、并查集三条路线怎么选同一个连通块计数问题至少有三套主流的实现方式。我给它们做了个对比方案核心思路额外空间适合场景主要风险DFS 递归朝一个方向挖到底再回溯递归栈最坏 O(N×M)入门理解、小地图图太大可能爆栈BFS 队列一层一层向外扩散队列最坏 O(N×M)地图较大、后续要求最短路入队时机写错会重复入队并查集相邻水格两两合并数根节点父数组 O(N×M)连接关系动态变化的场景方向逻辑错误隐蔽难查我的建议是入门阶段先把 DFS 递归版写熟因为它代码量最少和 Flood fill 的直觉最贴合。等递归理解扎实之后再去看 BFS 和并查集你会发现它们的底层思想其实完全一样只是扩散顺序和数据结构不同。这三套代码我会在第 3 章全部给出。3. 三套可提交代码逐行拆解3.1 DFS 递归版最短最贴近直觉的写法先把 C 的 DFS 完整实现放出来这是我最推荐入门使用的版本#include bits/stdc.h using namespace std; const int MAXN 105; int n, m; char grid[MAXN][MAXN]; bool vis[MAXN][MAXN]; int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1}; void dfs(int x, int y) { vis[x][y] true; 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 (grid[nx][ny] W !vis[nx][ny]) { dfs(nx, ny); } } } int main() { cin n m; for (int i 0; i n; i) { cin grid[i]; } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] W !vis[i][j]) { ans; dfs(i, j); } } } cout ans endl; return 0; }注意几个细节。cin grid[i]按字符串整行读入然后grid[i][j]就能直接访问第 i 行第 j 列的字符这是二维网格题最常用的读入方式。dfs函数一进来立刻做vis[x][y] true这一步在递归开头而不是在调用前是为了避免不同入口重复进入同一个格子。方向数组dx和dy是一一对应的(dx[k], dy[k])表示第 k 个方向的行偏移和列偏移。我把这 8 对偏移按顺时针排布从左上角开始这样可以保证遍历时不会凭手感漏项。如果用 Python 交这道题同样思路的代码长这样import sys sys.setrecursionlimit(1000000) n, m map(int, input().split()) grid [list(input().strip()) for _ in range(n)] vis [[False] * m for _ in range(n)] dx [-1, -1, -1, 0, 0, 1, 1, 1] dy [-1, 0, 1, -1, 1, -1, 0, 1] def dfs(x, y): vis[x][y] True for i in range(8): nx, ny x dx[i], y dy[i] if 0 nx n and 0 ny m and grid[nx][ny] W and not vis[nx][ny]: dfs(nx, ny) ans 0 for i in range(n): for j in range(m): if grid[i][j] W and not vis[i][j]: ans 1 dfs(i, j) print(ans)Python 里第一行sys.setrecursionlimit很重要。默认递归深度只有一千层左右如果地图是一个几千格连成一片的大池塘不调高递归限制就会直接 Runtime Error。C 其实也有类似的栈空间问题后面第 4 章会详细讲。3.2 BFS 队列版稳扎稳打的防爆栈选择如果地图规模很大或者你不想依赖递归栈BFS 是更稳的选择。它用队列代替递归一层一层向外扩散#include bits/stdc.h using namespace std; const int MAXN 105; int n, m; char grid[MAXN][MAXN]; bool vis[MAXN][MAXN]; 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}); vis[sx][sy] true; while (!q.empty()) { auto [x, y] q.front(); 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 (grid[nx][ny] W !vis[nx][ny]) { vis[nx][ny] true; q.push({nx, ny}); } } } } int main() { cin n m; for (int i 0; i n; i) cin grid[i]; int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] W !vis[i][j]) { ans; bfs(i, j); } } } cout ans endl; return 0; }BFS 的关键点和 DFS 有细微差别。标记vis的时机务必在节点入队的那一刻而不是出队的那一刻。如果在出队时才标记同一个格子可能会被多个邻居重复丢进队列导致大量冗余计算地图一大就直接超时。这个坑我当年踩过印象非常深刻。从理解角度说BFS 的扩散像水波一圈圈往外推而 DFS 更像一个执着的探险家沿着一条路走到底再回头。对这道题而言两者结果完全一样选择哪个主要看个人习惯和地图规模。3.3 并查集版从合并视角再看连通性前面两套方案都是从种子出发染色并查集换了一个角度直接扫描所有W格子把相邻的W全部合并到一个集合里最后统计共有多少个集合。#include bits/stdc.h using namespace std; const int MAXN 105; int n, m; char grid[MAXN][MAXN]; int fa[MAXN * MAXN]; int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1}; int id(int x, int y) { return x * m y; } int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void unite(int a, int b) { a find(a); b find(b); if (a ! b) fa[a] b; } int main() { cin n m; for (int i 0; i n; i) cin grid[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 (grid[i][j] ! W) continue; for (int k 0; k 8; k) { int ni i dx[k]; int nj j dy[k]; if (ni 0 || ni n || nj 0 || nj m) continue; if (grid[ni][nj] W) { unite(id(i, j), id(ni, nj)); } } } } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] W find(id(i, j)) id(i, j)) { ans; } } } cout ans endl; return 0; }并查集有几个细节值得说。id(x, y)把二维坐标映射成一维编号映射公式x * m y是网格题并查集的标配写法。find里用了路径压缩fa[x] find(fa[x])让每个节点直接指向根后续查找几乎是常数时间。最后统计答案时一个W格子如果是它所在集合的根就说明这是一个新池塘。这个版本的空间开销比 DFS/BFS 的vis数组略大因为需要保存每个格子的父节点但换来的是动态合并的能力。如果你以后遇到边添加边询问连通性这类题目这套模板能直接迁移过去。4. 评测翻车点这些坑我全踩过一遍4.1 方向数组漏项或重复一个方向的代价是 WA方向数组是八方向 Flood fill 里最隐蔽的雷区。我见过有人把dx、dy硬编码成 8 个方向结果里面有两个方向重复真正用到的只有 7 个也有人写 4 方向写习惯了把对角线全给漏了。检查方向数组有一个很笨但很有效的方法随便挑一个中间位置的格子比如 (2,2)手动把 8 个邻居坐标算出来再对着dx、dy逐项核对。坐标变换不复杂的但顺手写的方向数组往往错误必须用这种机械核对的方式确认。更稳妥的写法是使用二维方向数组int dir[8][2] { {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1} };这样每个方向的偏移一目了然不容易漏也不容易重复。4.2 标记遗漏的连锁反应标记vis的位置不对会导致两类典型的错误。第一种是彻底不标记。程序会在相邻格子之间无限递归最后爆栈或者超时。遇到这种问题先检查dfs函数第一行有没有vis[x][y] true。第二种更隐蔽发生在 BFS 中标记放在了出队时而不是入队时。结果就是一个格子可能被多个邻居分别入队虽然最终答案可能还是对的但队列里塞满冗余节点大数据直接 MLE 或 TLE。判别方法很简单在入队代码处打一行注释提醒自己入队即标记。如果你不想额外开vis数组也可以在访问过后直接把grid[i][j]改成.等价于给池塘抽干水。这在竞赛里很常见能省一点空间但务必要清楚原始数据已经被修改。4.3 输入读取和边界检查的隐形坑读入问题在字符串网格题里非常常见。cin n m之后如果直接getline读整行读到的会是第一行行尾残留的换行符导致后面每一行都错位最终地图少了第一行、多了一个空行。稳妥做法是用cin grid[i]按字符串读它会自动跳过空白字符或者先cin.ignore()再getline。边界检查这个坑更基础访问grid[nx][ny]之前必须先判断坐标是否越界。C 里越界访问是未定义行为不一定立刻崩溃但可能悄悄读到一个错误的值。养成习惯把越界判断写在最前面if (nx 0 || nx n || ny 0 || ny m) continue;顺序不要反先判边界再访问数组。4.4 一次完整的 WA 排查链路复盘我把这类题的排错过程完整复盘一次大家以后遇到可以照着这个思路走。我最初的版本是用四方向写的样例直接 WA因为样例里有两个W全靠对角线相连。于是我把方向数组补齐成 8 个方向样例通过了提交却还是 WA。接下来我做了几组手造测试。第一组全部是干地2 2 .. ..输出 0正确。第二组单独一个水格1 1 W输出 1正确。第三组是前面提过的对角样本2 2 W. .W按八方向应该是 1程序却输出 2。问题立刻锁定方向数组里有一条对角线没被触发。逐项打印每个方向的目标坐标后发现我在手写dx时把{1, 1}误写成了{1, 0}等于少了一个右下方向。修正后这组测试通过OJ 也 AC 了。这个排查链路的价值在于不要只依赖样例。样例只能覆盖最基本的情况一定要自己构造边界测试和特征测试尤其是小尺寸地图。1 行 1 列、全水、全干地、只有对角连通这四类测试是 Flood fill 题的标配自检集。5. 从 OJ 走向实战同一个 Flood fill 能干的远不止数池塘5.1 图像处理里的连通域标记Flood fill 在图像领域有个正式名字叫连通域标记Connected Component Labeling。二值图像里那些连成一片的白色区域就是一张巨大网格里的池塘。图像处理里统计目标个数、计算每个目标的面积、筛选最大连通域用的都是这套算法。图像领域的连通域通常也分四邻域和八邻域和这道题的差异一模一样。很多图像处理的初学者面对一堆专业术语觉得头大但如果先刷过「数池塘」这类 OJ 题再看连通域标记就会觉得非常亲切——无非是把字符数组换成像素数组。5.2 扫雷、地图区块和游戏开发中的应用游戏开发里 Flood fill 更是无处不在。扫雷游戏翻开空白格时一次性展开一大片区域用的就是 Flood fill只不过展开条件从是水变成了不是雷且周围没有雷。游戏地图中根据地形或海拔自动划分生态区域比如从一张噪声生成的地图上提取所有森林区块、水域区块也是同一套思路。做这类功能时方向选择要特别留意有些游戏规则里斜向不能穿墙那就得用四方向有些规则允许斜向移动就要用八方向。你现在提前在 OJ 上把这两种变体都练熟了后面写实际项目选型就会很有底气。5.3 顺着这道题继续往下刷什么如果你把「数池塘」彻底吃透了恭喜你已经拿到了连通块问题的基础模板。接下来可以按递进关系刷这些变体统计最大连通块的面积把ans改成在 DFS 里计数并维护最大值。连通块的外轮廓长度遍历时统计边界格子数量。需要把被包围区域填充掉先反向 Flood fill 边界再处理内部经典题如统计被包围的空白区域。动态网格的连通性查询配合并查集处理边破坏边查询的变体。我个人刷题的经验是不要急着追求一天刷很多道而是把一道题的三套写法全部写完再花时间构造测试用例去验证边界。这个过程对理解深度的影响远大于草草刷十道同类题。「数池塘」这道题我前后写了三版代码每换一种写法都能逼着自己重新审视一遍算法的本质这种基本功上的投入在后面的每一道图论题里都会加倍回报。