企业官网建设流程全解析

东方博宜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 递归版写熟，因为它代码量最少，和 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) { queue<pair<int, 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 边界，再处理内部（经典题如统计被包围的空白区域）。
• 动态网格的连通性查询：配合并查集处理"边破坏边查询"的变体。

我个人刷题的经验是，不要急着追求一天刷很多道，而是把一道题的三套写法全部写完，再花时间构造测试用例去验证边界。这个过程对理解深度的影响，远大于草草刷十道同类题。「数池塘」这道题我前后写了三版代码，每换一种写法都能逼着自己重新审视一遍算法的本质，这种基本功上的投入，在后面的每一道图论题里都会加倍回报。