最近好些初学者刷到东方博宜OJ 1435这道题数池塘八方向。评论区一水的在问为什么自己答案总差一两个或者运行直接崩了。其实这道题考察的就是非常典型的 Flood fill 算法——给定一张由字符组成的网格w表示水.表示陆地八方向连通的w算同一个池塘最后输出池塘总数。算法本身不难但细节一抓一堆很值得写一篇完整的复盘。这篇文章会从题目理解、算法选型、代码实现到常见坑位全部拆开讲适合刚入门DFS/BFS的人也适合想夯实连通块问题的算法竞赛选手。1. 题目到底在考什么先把这个“数池塘”掰开揉碎1.1 问题描述与样例解读东方博宜OJ 1435这道题输入一般长这样第一行两个整数 n 和 m代表网格有 n 行 m 列。接下来 n 行每行给一个长度为 m 的字符串字符串里只有两种字符我用最常见的约定来说明w 表示水格. 表示陆地格。题目要求数一数整个网格里有多少个池塘。这里的“池塘”不是单个水格而是由若干相邻水格组成的连通区域。注意“相邻”这个词在题面里明确限定为八方向也就是说某个水格自己周围的8个方向位置只要也是水格就和它是同一个池塘。对角线方向的格子也算相邻这是很多新手第一次容易忽略的地方。比如下面这个常见样例4 10 w........ .ww...... ..w...... ..w......第一行第一列是一个 w第二行第二列和第三列各有一个 w第三行第三列有一个 w第四行第三列有一个 w。如果只按四方向看这些 w 不一定都连在一起但按八方向看从 (0,0) 到 (1,1) 到 (2,2) 到 (3,2)每一个都能通过斜对角路径连起来所以它们属于同一个池塘答案应该是 1。这个例子很能说明八方向的意义一个水格不一定水平或垂直挨着另一个水格才连通斜着“搭边”也算连。所以做这道题脑子里得先建立起一个 8 邻域的坐标图而不是默认只做上下左右。1.2 八方向连通意味着什么如果把网格中的每个格子想象成一个点那么“八方向连通”的意思是每个点最多能连接到周围的8个点分别是左上、上、右上、左、右、左下、下、右下。对比我们熟悉的四方向八方向多引入了四个斜方向带来的直接影响是连通块更容易合并池塘数量会变少。举个例子两个 w 呈对角线分布w. .w四方向视角下这两个格子没有公共边会被当成两个独立的池塘八方向视角下它们通过对角相邻属于同一个池塘。所以代码里的方向偏移表必须包含 8 组坐标变化。少写一个斜方向或者只写了4组偏移都会导致答案比正确值偏大而且这种错误很难肉眼发现容易在边界数据上暴露。我自己的记忆方法是这样把方向数组拆成“行变化 dx”和“列变化 dy”按从左上角顺时针或者任意稳定顺序排列保证8个方向都覆盖到。比如int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1};这些数字分别对应左上、上、右上、左、右、左下、下、右下。方向顺序本身无所谓关键是8个组合一个都不能少。后面写循环的时候只要保证 nx x dx[i]ny y dy[i] 能覆盖整个 3x3 邻域即可。1.3 为什么这类题统一用 Flood fillFlood fill 翻译过来叫“洪水填充”它解决的问题就是从一个种子点出发扩散到所有与之连通的符合要求的点最终形成一个连通区域。你可以把它想象成把一滴墨水倒在纸上墨水会顺着纸张纹理向四周渗透直到被完整区域边界挡住。代码里做的就是这个渗透动作。在“数池塘”这个场景里每次遇到一个还没被访问过的 w池塘数量加一然后从这个格子的位置开始做 Flood fill把与之八方向连通的所有 w 都标记成已访问。标记完成之后再继续在网格里找下一个没有访问过的 w。这样每个池塘只会被计数一次因为一旦被 Flood fill 染过色就不会再作为新的种子出现。为什么这种题统一用 Flood fill因为本质上它就是在找二维矩阵中的连通分量。无论题目叫“数池塘”“岛屿数量”还是“图像连通域”底层的遍历方式都是同一套东西深搜或广搜加上访问标记。掌握了 Flood fill 的通用套路后面遇到 LeetCode 200 岛屿数量、扫雷展开空白区域、画图软件的油漆桶工具都是一通百通。2. Flood fill 的核心思路与方案选型2.1 把网格当成图来遍历很多人第一次接触 Flood fill 会觉得玄其实核心就一步把网格想象成一张图每个格子是一个节点两个格子之间如果满足相邻且同为 w就认为它们之间有一条边。我们要做的事情就是在这张隐式图上跑图的遍历算法把每个连通分量都访问一遍。图的存储不一定真的需要邻接表或邻接矩阵因为每个节点的邻居是可以通过坐标偏移现算的。代码里写一个 8 次循环每次算出候选坐标然后判断候选坐标是否越界、是否为目标字符就相当于在图里沿着某条边走到下一个节点。这种不需要显式建图的方式在网格类算法题里非常常见也被称为“隐式图遍历”。再进一步看Flood fill 的遍历顺序并不重要。你既可以从某个 w 开始一路往右下递归也可以借助队列一层一层向外扩散。最终效果都是把整个连通块完整“淹没”。因此选择 DFS 还是 BFS更多取决于你对递归的熟练度以及题目对栈空间的限制而不是算法正确性的区别。2.2 DFS 和 BFS 怎么选DFS深度优先搜索写起来最直观代码量也小。伪代码结构就是一个递归函数进函数先把自己标记成已访问然后遍历8个邻居遇到合法的 w 就继续递归调用。这个“一路走到黑”的搜索方式很适合初学者理解因为和“把墨水往一个方向倒”的直觉比较匹配。但 DFS 有一个明显问题递归深度等于当前连通块大小。如果 n 和 m 最大到 100全网格都是 w那么一个连通块可能包含 10000 个格子DFS 递归层数也可能接近 10000。这在大多数在线评测系统上问题不大但在本地默认栈上可能直接爆掉表现为程序异常退出。如果题目范围大到 1000×1000那就千万别用递归 DFS 硬碰老老实实换 BFS 或手写栈。BFS广度优先搜索的核心是用队列维护待访问节点。每从队头取出一个格子就把它的8个未访问邻居全部入队并立刻标记。它的好处是天然不会出现递归爆栈而且每个格子只入队一次比较稳定。坏处是要额外维护一个队列代码比递归 DFS 略微长一点但差距不大。对于“数池塘”这种格子数量不太夸张的题DFS 和 BFS 都能过选哪个都行。2.3 标记方式的两个流派做 Flood fill 一定要有“标记已访问”的机制否则一个池塘里的 w 会被反复当作新起点计数就乱了。最常见的做法有两种一是单独开一个二维 bool 数组 visited二是直接把原网格里的 w 改成 .。两种都有人用我推荐第二种因为代码更短、内存更省、思路也更粗暴。直接改原图的逻辑是只要一个水格被 Flood fill 访问过就把它改成陆地字符这样主循环再扫到它时不会触发 new count。比如 DFS 开头执行 grid[x][y] .相当于“把这一格的水抽干”。这个操作在算法题里非常常见像岛屿数量问题也经常用“沉岛”这个名字来描述。用 visited 数组则显得更“正统”适合你不想破坏原数据、或者后面还想继续用原始图的情况。但代价是多开一个同样大小的二维数组代码里每个格子访问前都要检查 visited 位。这道题原图用过一次就没用了所以直接原地标记更优雅。3. 手把手写出可 AC 的代码3.1 准备代码框架与数据读入先把头文件和主函数写好注意这道题读入的是字符串而不是单个字符这是很多人的第一个坑。如果你用 cin 的 操作符它会自动跳过空白字符空格、换行、Tab所以可以放心地一行一行读字符串。但如果用 scanf 或 cin.getline就要自己处理换行符残留问题比较麻烦。下面给出一个稳妥的 C 代码框架#include iostream using namespace std; const int MAXN 105; int n, m; char grid[MAXN][MAXN]; int main() { cin n m; for (int i 0; i n; i) { cin grid[i]; } // 后续统计逻辑在这里 return 0; }这段代码假设网格最大为 100×100开 105 的余量足够。如果你不确定题目范围可以稍微开大一点比如 1005 或 2005不会有什么副作用。读入每一行字符串时C 会自动在末尾补上 \0所以 grid[i] 可以直接当字符串访问也可以当字符数组按坐标访问。3.2 DFS 版本实现与逐行说明DFS 版本非常短。我们定义一个全局方向数组和递归函数函数作用是从 (x, y) 出发把所有连通的 w 都变成 .。注意递归之前必须先判断越界这一步千万别省否则数组越界访问会导致结果不可预期甚至直接运行时错误。完整代码如下#include iostream using namespace std; const int MAXN 105; int n, m; char grid[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) { grid[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 (grid[nx][ny] w) { dfs(nx, ny); } } } int main() { cin n m; for (int i 0; i n; i) { cin grid[i]; } int cnt 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] w) { cnt; dfs(i, j); } } } cout cnt endl; return 0; }逐行解释一下dfs 第一次进入时立刻把当前格改为 .避免后续重复访问。然后生成 8 个候选邻居坐标跳过越界的邻居如果邻居还是 w就继续递归。主循环从左上角到右下角扫整个网格每发现一个没被“抽干”的 w就认为找到了新池塘池塘数加一然后调用 dfs 抽干整个池塘。这段代码在大多数评测平台上都能 AC。需要留个心如果 n, m 最大到 500 以上递归深度就可能有点危险但数字不太大的情况下完全够用。3.3 BFS 版本实现与逐行说明BFS 版本适合对递归栈不放心、或者一开始就习惯用队列的读者。我们把 DFS 的递归调用改成队列的 push/pop同时仍然采用原地标记。BFS 的关键点在于入队的那一刻就要把格子改成 .而不是等弹出队列再标记。如果弹出时才标记同一个格子可能被多个邻居重复入队轻则浪费资源重则队列失控。完整代码如下#include iostream #include queue using namespace std; const int MAXN 105; int n, m; char grid[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}); grid[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 (grid[nx][ny] w) { grid[nx][ny] .; q.push({nx, ny}); } } } } int main() { cin n m; for (int i 0; i n; i) { cin grid[i]; } int cnt 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] w) { cnt; bfs(i, j); } } } cout cnt endl; return 0; }这段代码和 DFS 版本最终效果一样但运行过程完全不同。BFS 是一层一层往外扩散DFS 是一条路走到黑再回头。对于大多数数据规模两者效率都在同一量级不需要神化哪一个。如果你用的是较老版本的编译器记得包含 和 不过 C11 之后直接写 就能带上 pair 定义。3.4 复杂度分析跑得动吗复杂度是这类题必须懂的东西。每个格子最多只会被处理一次当它是 w 且尚未被访问时递归/入队当它已经被改成 . 后不会再作为新种子。每一次处理程序最多检查 8 个方向。所以时间复杂度是 O(8 * n * m)也就是 O(n * m)常数 8 不影响渐进复杂度。空间方面原地改图只用递归栈或队列BFS 最坏情况下队列可能存下一整块连通区域也就是 O(n * m)DFS 最坏递归深度也是 O(n * m)。对 100×100 甚至 200×200 的数据这个复杂度毫无压力。如果是 1000×1000 的满水网格BFS 队列可能要存 100 万个点内存大约几 MB也完全能承受。真正需要担心的是递归深度所以数据范围大的时候BFS 会是更稳妥的选择。4. 实战中的坑与排查实录4.1 字符读入与换行的坑这道题最容易翻车的第一步不是算法而是读入。有些人习惯用 cin.getline 或 scanf(%c) 逐字符读于是会把换行符也当成字符读进来。明明答案是 2结果代码跑出个 4因为网格里混入了许多 \n 字符它们不是 w但可能会影响你后续的判断逻辑尤其如果你用字符数组存储时位置错位整个网格都会乱掉。最省心的方法就是直接 cin grid[i]。因为 在读字符串时会自动跳过所有空白字符所以即使上一行结尾有回车也不会带进字符串中。如果你就是喜欢用 getline那么读完 n m 后需要先用 getchar() 或者 cin.ignore() 吃掉那一行的换行再逐行读字符串。这个细节在本地测试时不一定暴露因为输入数据可能没有多余空格但在测评系统里很致命。另外还有一个小坑当题目给的水格字符是大写 W你却用 w 去判断答案会变成 0。每次写题前先看清楚题面里的字符到底是大写还是小写我见过有些人死磕代码半天最后发现是大小写不对非常亏。4.2 方向数组写错导致的边界问题八方向的方向数组书写时很容易漏掉某一组偏移或者把两个偏移重复写成同一个。比如有人会写int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1};这是正确的。但如果你不小心把 dy 写成 {-1, 0, 1, -1, 1, -1, -1, 1}就会出现重复的方向导致某个斜方向没被检查到。这种错误在小的手写样例上很难发现因为只要是相邻的 w 还是能连通一部分但你一旦构造一个“只通过对角线相连”的特例答案立刻不对。我的建议是写完方向数组后对照坐标手动画一遍 3×3 表格确认从中心出发的 8 个方向都对应到了正确数值。也可以在自测时专门构造两个斜对角 w 的数据看看程序输出是否为 1这个反例能快速判断方向数组是不是漏方向。还有一点方向数组本身也有循环顺序但顺序不影响正确性。不要纠结于是从左上开始还是从右边开始重要的是覆盖全。代码里在每个方向上都进行越界检查否则 nx 或 ny 可能跑到 -1 或 n、m 之外。访问 grid[-1][0] 会读到一个未定义的值有时候是 .有时候是 0但无论如何都不是你预期中的情况。4.3 递归爆栈和重复计数递归 DFS 在连通块非常大时可能爆栈这是最让人头疼的运行错误之一。本机上可能跑得好好的一到评测机就崩溃原因就是系统栈空间受限。如果题目范围较大或者你不想担心递归深度直接用 BFS 版本就好。有些人会尝试在编译选项里增加栈空间但这不是通用解法换 BFS 才是正道。重复计数问题多半出在标记时机不对。主循环发现一个 w 后调用了 DFSDFS 内部如果没在进入格子时立刻把 grid[x][y] 改成 .那么同一个池塘里被其他路径访问到的 w 还会再次被当作新起点cnt 会被重复加很多次。正确做法是只要一个 w 被“染色”就要立刻标记不能等到递归返回再处理。BFS 同理入队即标记延迟标记会带来重复入队。4.4 常见问题速查表把实际调试中容易踩的问题整理成一个表方便你写完代码后逐项对照问题现象可能原因处理方法答案比正确值大方向数组漏了斜方向实际变成四方向检查 dx/dy 是否有 8 组不重复偏移答案明显异常偏大大小写字符写反没识别到水格确认题面中是 w 还是 W答案偏小标记不及时导致某些池塘没被完全染色确保进入格子/入队时立即标记运行直接崩溃递归深度过大换成 BFS 或手写栈输出总是 0读入方式错误网格数据错位用 cin grid[i] 或先吃掉换行符本地正确测评不对数组开小了检查题目范围适当扩大数组常量编译错误没包含 queue 或 utility加上 #include这表里每一条我都实际见过。尤其是“答案比正确值大”这一点十个人里有七八个都是因为方向数组写不全所以代码写完后第一件事不是急着交而是自己构造一个斜对角连通的反例测一下。5. 做完这道题之后的个人体会5.1 我的做题习惯和自测方法每次刷完这种 Flood fill 题我都会留几分钟做三件事第一检查方向数组第二构造极端数据第三把 DFS 和 BFS 的结果互相对拍。互拍是个很笨但很有效的方法尤其在做竞赛题的时候两种实现跑同一组随机数据只要输出不一致一定有一份代码存在隐藏问题。还有一个我很推荐的自测技巧把所有格子全部填成 w比如 5 行 5 列全是水。这个数据在八方向下会连通成一个池塘正确答案必然是 1。如果程序输出大于 1说明标记逻辑或扫描逻辑有问题。同样把所有格子全部填成 .正确答案必然是 0可以测出是否误判。这种极端数据比随机数据更容易暴露逻辑硬伤。在学 Flood fill 的时候我还习惯准备一张纸自己随手画几个“L”形水池和“X”形水池手动数一遍再用程序跑一遍。手动数的好处是让你真的理解连通块的概念而不是只靠代码跑出结果。尤其是八方向连通纸上演练一遍后你对八方向的分组记忆会深刻很多。5.2 这道题的扩展方向打通了这道题后面很多题都会轻松很多。最典型的是坑爹的“岛屿数量”问题它通常只要求四方向但核心思路和这道题一模一样。再比如扫雷游戏里点击一张空白格子时要展开一大片空白区域用的也是 Flood fill 的思路只是颜色或数字的判断条件不同。图像处理里的区域填充、迷宫寻找可到达区域底层同样是这套遍历。如果你想进阶一点还可以用并查集Union-Find来做这道题遍历所有 w 格子把八方向相邻的 w 合并到同一个集合最后统计集合个数。这和 Flood fill 的复杂度差不多但思考角度完全不一样适合用来对比理解“连通分量”的多种实现方式。不过当前阶段掌握 DFS/BFS 版本的 Flood fill 已经足够剩下的可以等遇到具体题目再慢慢扩展。最后分享一个我自己的小习惯写 Flood fill 时永远把方向数组定义成全局变量并且放在代码最显眼的位置。这样每次调试时第一眼就能看到它不容易因为重复修改局部变量而出错。这种细节看似不起眼却在比赛和刷题时帮你省下大把时间。