数池塘四方向题解：吃透Flood fill与DFS/BFS核心写法

做算法题这几年有个很深的体会很多看起来“基础”的题目其实才是最能拉开差距的地方。就拿东方博宜OJ上的1434题“数池塘四方向”来说单看名字平平无奇无非就是统计一个矩阵里有几块水域但真正把它吃透你对Flood fill的理解、对DFS/BFS两种写法的掌握、对边界条件的敏感度都会上一个台阶。这篇文章我想把这个题掰开了讲从题意分析、两种核心写法的对比、四方向和八方向的区别到常见报错和调试技巧一次性说清楚。1. 题目拆解与核心思路1.1 题意到底在说什么先看题目本身。输入是一个由字符组成的矩阵通常用W表示水坑Water.表示干地Land整个矩阵代表一片被划分成方格的土地。题目要求统计共有多少个“池塘”而“池塘”的定义是上下左右四个方向上相邻的W连成的一个连通块。这点很关键。所谓的“四方向”指的是对一个格子而言只有上up、下down、左left、右right四个邻居能被视为“同一片池塘”斜对角方向的W即使紧挨着也不算连在一起。很多新手第一次做这道题容易下意识把斜对角也算进去那结果就会比正确答案多出不少连通块。题目要求输出的就是一个整数代表池塘的个数。数据范围我印象中矩阵的行列都在100以内规模不算大暴力深搜或者广搜都能过但这道题真正的价值不在于“能不能跑完”而在于你有没有把Flood fill的思路吃透。1.2 为什么暴力枚举不可行有的同学可能会想那我直接双重循环遍历每个格子碰到W就把它周围的W都标记一下不就能统计出来了吗这个想法方向没错但问题在于“把周围所有连通的W都标记出来”这件事本身没有那么简单。比如一个形状像螺旋一样的水域从左上角的W出发你如果不做遍历只是单纯看“上下左右有没有W”那是没办法把一整片螺旋形池塘完整找出来的。更麻烦的是同一片池塘可能在遍历过程中被重复计数比如你先从(0,0)这个W开始数了一次后面遍历到(0,1)时发现它也是W如果不加判断又把它当成一个新池塘结果就错了。所以正确的思路必须是每遇到一个未被访问过的W就把它所在的整个连通块完整地“染色”一遍让这片池塘里所有的W都变成“已访问”状态这样后续遍历再遇到它们时就不会重复计数。这个“染色”过程就是Flood fill算法的核心。2. Flood fill的两种经典实现2.1 DFS写法递归的力量理解DFS深度优先搜索的写法关键要抓住三个要素当前格子坐标、访问标记、方向的扩展。我先给出一个最典型的代码模板后面再逐行解释。#include iostream using namespace std; int n, m; char grid[105][105]; int visited[105][105]; // 四方向数组上、下、左、右 int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; void dfs(int x, int y) { visited[x][y] 1; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 nx n ny 0 ny m grid[nx][ny] W !visited[nx][ny]) { dfs(nx, ny); } } } int main() { cin n m; for (int i 0; i n; i) { for (int j 0; j m; j) { cin grid[i][j]; } } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] W !visited[i][j]) { ans; dfs(i, j); } } } cout ans endl; return 0; }这段代码的核心逻辑其实只有两个循环外层循环负责找到新池塘的起点内层的dfs负责把整片池塘染色。我当年第一次看这个题的时候始终想不明白一个问题“为什么主函数里每次碰到一个没访问过的W主动ans之后调用dfs就能保证这个W和之前统计过的池塘不重叠”答案是所有之前已经被统计过的池塘里面的每个W都会被标记成visited 1所以主循环遍历到它们的时候因为!visited[i][j]这个条件不成立根本就不会进入ans分支。我想特别提醒一个初学者很容易犯的错有些同学会在dfs内部也写ans这基本必错。ans的计数应该只发生在“发现了新连通块起点”的那一刻等dfs扩散完后这片池塘已经被整体标记了不能再被当作新池塘。如果你在递归里计数那同一片池塘会被数出很多次答案会变成一个很大的错误数字。2.2 BFS写法队列的妙用BFS广度优先搜索写法的思路和DFS本质上是一样的只不过“染色”的顺序不同。DFS是一条路走到黑撞到边界再回头BFS则是像涟漪一样一圈一圈向外扩散。BFS需要用到队列queue代码长一点但对某些场景更顺手。#include iostream #include queue using namespace std; int n, m; char grid[105][105]; int visited[105][105]; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; void bfs(int x, int y) { queuepairint, int q; q.push({x, y}); visited[x][y] 1; while (!q.empty()) { int cx q.front().first; int cy q.front().second; q.pop(); for (int i 0; i 4; i) { int nx cx dx[i]; int ny cy dy[i]; if (nx 0 nx n ny 0 ny m grid[nx][ny] W !visited[nx][ny]) { visited[nx][ny] 1; q.push({nx, ny}); } } } } int main() { cin n m; for (int i 0; i n; i) { for (int j 0; j m; j) { cin grid[i][j]; } } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] W !visited[i][j]) { ans; bfs(i, j); } } } cout ans endl; return 0; }BFS写法里有一个细节我反复跟人强调过在把邻居节点加入队列的那一刻就要立刻标记visited而不是等它出队时再标记。为什么因为如果不立刻标记同一个格子可能被多个方向同时发现然后被重复加入队列。虽然这不会导致答案错误但会导致队列里多出大量重复元素在矩阵规模大的时候明显拖慢速度严重的还可能造成超时。2.3 两种写法该怎么选说实话对于数池塘这道题的数据范围DFS和BFS在效率上没有本质区别选哪种全看你个人的熟练度。但我个人的经验是如果你刚学Flood fill请先死磕BFS写法。理由很简单DFS虽然代码短但它的递归调用在迷宫规模极大比如1000x1000的矩阵都是W时可能因为递归层数太深导致爆栈。很多OJ上的题目数据范围看着不大但出题人可能会在同题异构的进阶版本里偷偷把范围拉大这时候DFS直接运行报错你还得额外改成栈模拟BFS就没有这个问题。此外BFS天然带有“距离由近到远”的性质将来遇到要统计连通块大小、求最短步数这类题目时队列里的数据天然分层改起来很顺手。DFS则更适合在需要输出具体路径、或者回溯剪枝的场景中用。早点把两种写法都练熟日后遇到题目就能根据需求灵活切换。3. 四方向与八方向差之一字谬之千里3.1 方向数组到底在表达什么很多初学者误以为四方向只是把dx、dy数组从4个元素改成8个元素那么简单。对也不对。改方向数组的确是最直观的一步但背后涉及的是逻辑上对“连通性”定义的根本改变。先看四方向的方向定义。如果你把矩阵想象成一张地图坐标轴是x行、y列那么四方向对应的偏移量就是方向dx行偏移dy列偏移上-10下10左0-1右01注意这里x减一是“向上”走x加一是“向下”走和我们在直角坐标系里的习惯正好相反。因为二维数组的第一维度行号是自上而下增长的。这个点如果没想清楚写代码时很容易把上下方向搞反虽然对最终答案可能没影响四个方向都遍历了但解题幸福感会大打折扣。八方向相对就复杂一些除了上下左右还要加入左上、右上、左下、右下四个斜向。方向数组变成int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1};四方向中坐标(0,0)和(1,1)虽然在对角线上紧挨着但它们不算连通在八方向中它们就是同一个连通块。3.2 实战中如何确认题目要哪种这看起来是个很简单的问题但在东方博宜OJ上同一个“数池塘”题目其实有两个版本一个要求四方向一个要求八方向。如果你拿四方向的代码去交八方向的题结果大概率是答案偏大因为本该连成一片的池塘被你拆成了多块反过来如果你拿八方向的模板去交四方向的题答案就偏小因为多个不同的池塘被错误地合并成了一片。我强烈建议拿到任何搜索题第一步不是急着写代码而是把题目里的“相邻”定义圈出来。题目里写“上下左右”就是四方向写“八个方向”或“周围八格”就是八方向。有时候题目还会表述成“只能水平或垂直移动”这时候也必然是四方向。看清题目再动手能省掉后面一整轮的排查时间。3.3 方向顺序会影响答案和效率吗对答案不会对运行效率可能有微妙影响但通常可以忽略。DFS递归时四个方向的搜索顺序在逻辑上等价因为最终都会遍历完同一个连通块。唯一可能产生差别的是递归栈的深度轨迹在极端地形下某个方向优先会先碰到底但这对现代计算机来说微不足道。不过有一个例外如果题目要求输出连通块内格子坐标的某种顺序比如按字典序那方向数组的顺序就需要刻意设计了。数池塘这道题没有这种要求所以你可以按舒服的顺序写。我自己习惯按上、下、左、右排和很多教材保持一致方便记忆不易在比赛中手滑写错。4. 边界处理与visited标记的深层逻辑4.1 越界检查为什么必须放在最前面新手写DFS/BFS时最容易出的问题就是在递归函数里访问了不存在的格子坐标程序直接在运行期报段错误segmentation fault。比如当前点在(0,0)你往上走变成(-1,0)这时候如果直接访问grid[-1][0]数组下标越界行为是未定义的。常见的误区是把越界检查放在grid[nx][ny] W之后。比如有人会这样写if (grid[nx][ny] W nx 0 nx n ny 0 ny m !visited[nx][ny])这种写法是错的因为C在计算表达式时是从左到右依次求值的一旦grid[nx][ny]先被访问而nx已经越界程序已经出错了。必须保证边界检查永远最先执行if (nx 0 nx n ny 0 ny m grid[nx][ny] W !visited[nx][ny])你可以把理解为“关卡”越界检查是第一道关字符判断是第二道关访问标记是第三道关。顺序错了后面两关形同虚设。4.2 能否原地修改grid代替visited数组代码里能省则省是很多选手的追求有同学会想既然要标记已访问那直接把这个格子从W改成.不就行了吗确实可以实际上很多工整的题解就是这么干的。这种做法在竞赛中很常见还能省掉一个数组的内存空间。void dfs(int x, int y) { grid[x][y] .; // 直接把水坑改成陆地相当于标记已访问 for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 nx n ny 0 ny m grid[nx][ny] W) { dfs(nx, ny); } } }我个人建议初学阶段老老实实用visited数组。原因有二。第一调试的时候你还能看到原始地图长什么样方便你肉眼追踪搜索过程如果直接把grid改了调试时一片模糊。第二有的进阶题目后续还需要用原图做别的计算你提前破坏了原始数据会陷入被动。等你对Flood fill完全驾轻就熟再考虑空间优化不迟。4.3 连通块遍历的终止条件什么时候算“这一片池塘找完了”从算法角度来说就是当队列为空BFS或递归自然返回DFS时。递归的自然返回没有显式的return是因为函数体执行完就自动返回了。每一个格子都被访问过它的四个方向要么越界、要么不是水、要么已被标记没有新的可扩展点递归就层层退出。这里有个小技巧如果你在递归函数末尾打印一下当前坐标和走向就能很直观地看到搜索轨迹。我在本地调试时特别喜欢加一句cout visiting: x , y endl;看几组数据之后对递归的顺序感受完全不同。做题不光为了AC更为了真正理解。花十分钟观察这个过程比刷十道题更值。5. 完整提交流程与细节优化5.1 从读入到输出的完整流程这道题的输入格式通常是第一行两个整数n和m表示行数和列数接下来n行每行m个字符中间没有空格。读入的时候用cin grid[i][j]即可自动跳过空白字符。完整流程可以总结成四步读入矩阵的尺寸和内容。初始化visited为0全局数组默认已是0但显式重置更稳妥。双重循环遍历每个格子遇到未访问的W就计数并调用搜索函数。输出总数。我见过一个坑是有人把n和m读反了导致双重循环越界或者遍历范围不够。题目里如果明确写了“n代表行m代表列”就老老实实按这个来不要想当然认为第一个数字一定是行。养成读入后看一眼实际数据的习惯能帮你避开这种低级失误。5.2 使用全局数组的好处做题时我倾向于把所有数组和递归函数都定义在全局作用域而不是main函数内部。为什么第一全局数组默认自动初始化为0省去memset的工作第二dfs递归函数访问全局变量不需要通过参数传递矩阵和标记数组函数签名简洁很多出错率低第三全局数组开在静态区不会因为栈空间不足而崩溃。放到main内部定义数组当然也可以但局部数组存储在栈上极端情况下大数组可能导致栈溢出。虽然本题100x100的规模远不至于但从一开始养成好习惯后面遇到更大规模的题目就不慌。我还习惯为数组多留一点余量比如题目说最多100我就开105宁可多几行内存不给越界留机会。5.3 代码风格与可读性建议竞赛博主有时候喜欢把代码压到最短但我不推荐初学者追求这个。我自己的习惯是变量名尽量有意义grid就是地图visited就是访问标记dfs、bfs就是函数名一眼看懂。方向数组固定命名为dx和dy这也是社区通用命名写比赛时能减少思考成本。在东方博宜OJ这类在线评测平台上提交编译环境通常是C17上面的代码直接就能通过。如果你的编译器提示pair找不到记得包含utility头文件不过通常iostream和queue已经间接包含了问题不大。还是那句话与其纠结这些细枝末节不如把时间花在理解算法上。6. 常见错误与调试技巧实录6.1 答案偏大的原因分析用四方向代码做完题如果你的输出比正确答案大优先检查以下三处。visited标记遗漏。有些格子明明属于同一片池塘但因为标记条件写错导致被重复计数。方向数组写错。比如把四方向的dx、dy误填成八方向的长度导致本该连通的格子没走通。递归入口条件放宽。比如判断grid[nx][ny] W时没有加上!visited[nx][ny]但这反而会导致重复入队答案偏大的概率反而较低最典型的还是前面说的在递归里计数。6.2 答案偏小的原因分析答案偏小则通常是过度合并了池塘。最常见的情况是用八方向代码去做四方向的题。斜对角的水域被错误地并入了同一块池塘个数自然变少。还有就是边界处理时某些W被错误地改成了.或visited被错误标记为1导致本应独立的连通块没被计数。这类问题最难查因为代码逻辑看着没问题只有在你用一个小规模样例手工模拟时才能发现。6.3 两个经典小样例帮你验证代码我每次写完Flood fill类题目都会先用下面这些小样例验证一遍。样例一单块小池塘3 3 W.. .W. ..W对角线上有三个W但四方向规则下它们互不相邻应该输出3。样例二两块独立的池塘3 4 WW.. ..WW .....第一行WW是一块第二行WW是另一块输出2。如果把两个WW放成对角线相邻四方向依然是2八方向就会变成1。跑通这两个样例你的核心逻辑基本就稳了。调试时还可以故意加大矩阵尺寸比如100行100列全部填W看程序是否能在几百毫秒内跑完。这能验证代码在极端全连通情况下的效率和递归深度是否安全。6.4 我的本地调试小工具我想分享一个比较个人化的习惯本地调试时我会在搜索前后分别打印矩阵标记被访问的格子。简单做法是在递归函数开头临时加一行把当前格子改成小写字母或数字这样在终端里能清晰看到“染色”的过程。void dfs(int x, int y) { grid[x][y] *; // 临时标记方便观察 // ... }注意交题之前一定记得把这些调试代码删掉或者用#ifdef LOCAL之类的宏包起来不然输出格式会被破坏评测直接判WA。我当年就干过这种蠢事本地跑得好好的一提交全错检查半小时发现是调试输出混进了结果里。从那以后我写任何题目都养成“提交前通读一遍主输出逻辑”的习惯。7. 从数池塘到更广阔的搜索世界7.1 同类型题目的一通百通数池塘这道题看似简单但它其实是无数经典搜索题的“内核”。最典型的就是LeetCode上的“岛屿数量”问题给的矩阵由1和0组成让你统计岛屿个数本质上就是统计四方向连通块的数量。你再想远一点图像处理里的“连通区域标记”算法、扫地机器人做区域覆盖时的地图分割、迷宫寻路里的可达性判断底层全都是这一套Flood fill思想。我建议做完1434题之后顺手把以下几类变体都练一遍统计每个连通块的大小在DFS/BFS里加一个计数器。找出最大的连通块。判断一个特定坐标所在的连通块包含哪些格子。改造为八方向版本。这些变体每改一个条件你对这道题的掌握就深一层。等到下次在比赛中遇到陌生题目你就会条件反射地想“这不就是Flood fill的换皮版本吗”7.2 进阶路径压缩用并查集如果说Flood fill是“连续染色”的思路那并查集则是“按需合并”的思路。你可以把每个W都看作一个孤立节点然后检查相邻的W把它们合并到同一个集合里。最后统计有多少个集合就是池塘数。两种方法的时间和空间复杂度在本题量级下相差不大但并查集在一些特殊场景下更灵活。比如题目中途可能会修改地图上某个格子的状态或者需要动态询问两个格子是否连通这时候Flood fill每次都要重跑一遍并查集却可以增量更新。当然这是后话就数池塘这道题而言Flood fill是最直观、最好写、最不易错的方案。7.3 我对数池塘这道题的整体评价东方博宜OJ把这道题放在基础位置是有道理的。它没有复杂的数学变形没有刁钻的边界条件连“四方向”都在题目名字里明明白白写好了。但它恰恰能让老师一眼看出你是不是真正理解了搜索的精髓标记状态、遍历邻居、避免重复计数。这三个词听起来简单能做到不犯错全靠大量练习堆积。我自己带过一些学弟学妹有人一眼就会写有人看题解恍然大悟但过两周再遇到类似题又卡住了。差别就在于有没有真的跑过样例、画过递归流程、亲手调试过某个困住自己的错误。所以我还是那句话别看这道题简单务必亲手提交一次务必亲手造几个样例验证它。8. 一些实战中的个人心得最后还想再多说几句关于解题心态的话。数池塘这类Flood fill题目是少有的“能做对很容易、能做快也不难、但做得好需要积累”的题型。你不需要掌握什么高深的优化技巧只要抱着朴素的想法——把每片池塘都“淹没”一遍——代码自然就写出来了。有几个可以提高解题速度的小习惯我很受用。写方向数组时永远先想清楚dx和dy的对应关系再动手尽量在纸上勾勒出矩阵的坐标轴把“上减下加左减右加”这种口号背熟能省不少心。再比如所有搜索题的入口判断一定要简单统一我习惯用“当前格子未访问且满足题目条件”其他特殊情况一律交给递归内部处理。回到1434这道题本身四方向Flood fill只是第一步我知道好多同学是做完它才真正分清DFS和BFS的适用场景的。如果你能顺着这个思路把“数池塘”这个系列的每一道变体都吃透那你的图论搜索基础就算是真正夯实了。以后再遇到什么迷宫、扫雷、棋盘染色之类的问题都会感觉格外亲切因为它们的内核早在你做这道“简单”题时就已经埋下了。