在算法训练里Flood fill 几乎算是一道绕不开的“入门关卡”。东方博宜OJ 1435这道题名字叫“数池塘八方向”题面和农业、水域有关给你一张由字符组成的网格地图W代表水塘.代表旱地让你统计到底有几片池塘。本质上它就是在考连通块计数而连通块计数最经典、最直接的解法就是Flood fill洪泛填充这也是图像处理里“油漆桶”工具背后那套思路。刷过算法题的人都知道这道题难度不高但非常适合用来建立对DFS、BFS和连通性的直觉尤其适合刚接触搜索算法的初学者。我见过不少人把八方向写成四方向、把访问标记漏掉导致死循环甚至因为字符读入的换行问题卡了半天所以今天这篇就把这道题从头到尾拆透。1. 题目拆解数池塘到底在考什么1.1 先读懂题意什么算一个池塘题目输入很简单第一行两个整数n和m表示网格有n行m列。接下来是一个n乘m的字符矩阵矩阵里只有两种字符W表示水坑.表示干地。现在问你整张地图上有多少个池塘。关键不在字符本身而在“池塘”的定义。题目说的池塘是指一块由相邻的W连成的水域一整块W区域算一个池塘。这里“相邻”包含上下左右以及四条对角线也就是说从一个W出发周围一圈8个格子里的W全都跟它是连通的。只要两块W能直接相邻或者通过其他W间接连通它们就算同一个池塘。举个例子如果地图是这样的W.W. .WW. .W..那么第1行第1列的W自己孤零零的算一个池塘而右上角的W和中间一行的两个W、左下方一个W通过八方向连成了一片算另一个池塘。最终答案是2。这个“连成一片的区域算一个”的概念就是连通块。整个题其实就是让你数这张图里有多少个W连通块。1.2 为什么一看到“连通”就该想到Flood fill按名字理解Flood fill就是“洪水填充”。设想一下你往某个水坑倒一桶染料染料会顺着所有连通的W扩散开把整片池塘都染上颜色直到边界为止。这样操作一次你就“消化”掉了一个池塘然后再去找下一个还没被染色的W继续倒染料。每次倒染料代表的都是一个独立池塘倒了几次答案就是几。这是整个算法最核心的思想遍历所有格子只要遇到一个没处理过的W就说明发现了一个新的池塘计数加一然后从它出发把这个W所能到达的所有W全部标记成“已处理”。后续再扫到这些格子时就会直接跳过不会重复计数。把这个思路落到代码上就是最标准的Flood fill。Flood fill之所以是这类连通块题目的首选因为它的实现简单、直观而且时间复杂度和地图规模成线性关系整个图遍历一遍就能统计出所有连通块。相比之下如果你用“数一数有几个W”的朴素思路就完全没法处理“哪些W算同一片池塘”的连通关系答案是必错的。所以看到“连通”“相邻”“一片区域”这类词条件反射就应该是这题用Flood fill。1.3 四方向和八方向差一不注意就丢分“八方向”是这道题最容易翻车的点。很多人在学Flood fill、做岛屿数量类题目时默认都是四方向也就是只走上、下、左、右。比如LeetCode 200“岛屿数量”陆地的连接就是四方向。但东方博宜OJ 1435把条件放宽到了八方向也就是说对角线上的W也算相邻。这一改影响的不是一个判断条件而是整个搜索时的扩展方式。四方向从当前格子出发只能看4个邻居八方向要额外看4个对角线邻居。做搜索时方向数组从4组变成8组漏一组都不行。八方向的方向数组一般这么写int dx[8] {-1, 1, 0, 0, -1, -1, 1, 1}; int dy[8] {0, 0, -1, 1, -1, 1, -1, 1};每一组(dx[i], dy[i])代表一个相对偏移(-1, 0)是上一格(1, 0)是下一格(0, -1)是左一格(0, 1)是右一格剩下的四组正好对应左上、右上、左下、右下四个对角线方向。顺序无所谓但8组必须齐。如果你只写前后左右四个方向提交后答案大概率偏大因为很多本来通过对角线连成一体的池塘会被你拆成好几个。2. 核心实现两种Flood fill写法都要掌握2.1 深度优先DFS版本代码最短适合入门Flood fill最直观的写法是DFS也就是递归地往外扩展。从一个W格子出发递归地去访问它周围的8个邻居邻居如果是W就继续递归直到没有可扩展的邻居为止。DFS的完整代码如下#include iostream using namespace std; int n, m, ans; char a[105][105]; 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) { a[x][y] .; // 访问过就把W改成.相当于染色标记 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 a[nx][ny] W) { dfs(nx, ny); } } } int main() { cin n m; for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j]; } } for (int i 0; i n; i) { for (int j 0; j m; j) { if (a[i][j] W) { ans; dfs(i, j); } } } cout ans endl; return 0; }这套代码里有个很聪明的细节不需要额外开一个二维vis数组来标记哪些格子访问过而是直接把访问过的W改成.。反正这个格子已经属于当前正在统计的池塘之后无论从哪个入口进入搜索它都不会再被当作新池塘的起点。这种“原地染色”的技巧能节省内存也让代码更简洁。在dfs函数内部边界判断必须写在访问数组之前。原因很简单如果不先判断nx和ny是否越界直接去访问a[nx][ny]那么当坐标越界时就会读到数组外的垃圾数据轻则逻辑混乱重则直接Runtime Error。常见的写法就是先用四个布尔表达式把边界卡住确保只有合法坐标才进入下一步判断。2.2 广度优先BFS版本更稳不怕递归爆炸DFS简洁但不是没有代价。递归调用会占用系统栈空间如果一张地图特别大或者有一片巨大的W区域递归深度可能非常深深到把系统栈撑爆程序直接崩溃。这时候BFS的队列实现就体现出优势了BFS用队列保存待扩展的格子一层一层向外扩完全不依赖递归也就不存在栈溢出问题。BFS版本的代码如下#include iostream #include queue using namespace std; int n, m, ans; char a[105][105]; int dx[8] {-1, 1, 0, 0, -1, -1, 1, 1}; int dy[8] {0, 0, -1, 1, -1, 1, -1, 1}; void bfs(int x, int y) { queuepairint, int q; q.push({x, y}); a[x][y] .; while (!q.empty()) { auto cur q.front(); q.pop(); for (int i 0; i 8; i) { int nx cur.first dx[i]; int ny cur.second dy[i]; if (nx 0 nx n ny 0 ny m a[nx][ny] W) { a[nx][ny] .; q.push({nx, ny}); } } } } int main() { cin n m; for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j]; } } for (int i 0; i n; i) { for (int j 0; j m; j) { if (a[i][j] W) { ans; bfs(i, j); } } } cout ans endl; return 0; }注意BFS里的一个细节每当一个格子满足条件被加入到队列时就立刻把它改成.而不是等它出队时再改。这个顺序很关键。如果等到出队才标记同一个格子可能被多个邻居重复入队队列里会出现大量冗余节点在某些连通性很强的图里会白白增加好几倍的运算量。入队即标记是BFS处理二维网格的经典优化也是我经常强调的“入队时染色”原则。2.3 DFS和BFS怎么选从数据规模出发我给学生讲这道题时每次都会让他们把DFS和BFS各写一遍因为两种思路各有适用场景。从时间复杂度的角度看DFS和BFS完全一样都是O(n乘m)因为每个格子最多被入队或者递归访问一次。空间复杂度上的差异主要体现在“单次搜索撑开的规模”DFS依赖递归栈栈深等于当前连通块中从起点到最远点的递归路径长度BFS依赖队列队列最长的时候往往出现在地图有一片特别宽大的连通区域时。在极端情况下比如一张2000乘2000的图全是WDFS的递归深度可能会达到几十万层这在很多评测环境下已经非常危险而BFS队列存储的节点数量最多也就是地图总格数也就是400万左右通常可控。东方博宜OJ 1435的数据范围我记得n和m都不会太大用DFS完全没问题。但如果平时训练想培养稳妥的做题习惯建议小数据用DFS快速验证思路正式处理规模不确定的题时优先选择BFS。尤其是在面试或竞赛中栈溢出是Runtime Error里最让人头疼的一种而BFS能帮你彻底避开这个雷区。3. 逐行拆解提交过程与关键细节3.1 字符地图的读入cin、scanf与换行符很多刚接触字符矩阵的人会在读入上翻车。先说你用cin读字符的情况cin有一个特性它会自动跳过空白字符包括空格、换行符和制表符。所以这种代码for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j]; } }是可以正确工作的。第一行的n和m读完剩下的换行符会被cin自动跳过接着读到的第一个字符就是地图第一行的第一个字符中间哪怕有换行也不会被读进数组里。但如果用的是scanf配合%c读单个字符问题就来了。%c不会自动跳过任何空白字符你把上一行的换行符留在了输入缓冲区下一句scanf(%c, a[i][j])读到的就会是那个换行符整个地图数据全部错位。这种错的表现为你一输出整个地图第一列全是莫名其妙的空白或者答案出现明显的偏差。用scanf读字符矩阵时要么在%d后面手动吃一次getchar()要么用scanf( %c, a[i][j])——注意%c前面加一个空格让scanf先跳过空白字符再读。这也是我平时更推荐cin读字符的原因代码更简洁还少踩一类坑。3.2 坐标从0还是从1两种习惯的边界判断我前面给的代码用的是0下标也就是数组从a[0][0]开始读边界判断写成nx 0 nx n。这种写法符合C数组的原生形态写起来麻烦一点点但不容易搞错下标。另一种常见做法是用1下标也就是从a[1][1]开始存整个地图外围留一圈空边界这圈边界初始值是\0或.都无所谓因为搜索时只需关注实际地图范围。用1下标时读入循环是这样的for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; } }边界判断则简化成nx 1 nx n ny 1 ny m。1下标的好处在于它和日常坐标习惯一致第1行第1列就是地图左上角不容易在坐标换算上头晕。两种写法都能过但我个人建议初学者固定用其中一种反复多练几道题直到形成肌肉记忆省得每次写题都在边界判断上犹豫。无论是0下标还是1下标方向数组都是一样的。真正容易写错的是循环里的j是不是从0开始、m和n哪个对应行哪个对应列。先把n当作行数、m当作列数方向变化只在一二维坐标上做算术思路会清晰很多。3.3 自造样例验证手动模拟一遍Flood fill拿到这种题跑通代码之前先自己手算一遍样例非常有必要。我给你一个自造的简单用例3 4 W.W. .WW. W...手动模拟一遍第一步从第0行第0列开始扫发现a[0][0]是Wans变成1进入dfs。 从这个格子出发可以到达8个邻居中所有的W。第0行第2列是W第1行第1列是W第1行第2列也是W。继续向下扩展后第2行第0列的W也会被访问到。整个过程中所有被dfs染成.的格子组成了第一个池塘。继续扫描整张图剩下的格子全部是.没有新的W出现所以最终ans1。你也许会想右上角那个W和左下角那个W不是离得很远吗但是它们通过中间交叉的斜线连成了一个整体这正是八方向搜索的意义所在。如果这个题改成四方向那这几个W就会被拆成两个甚至三个池塘答案就完全不一样了。提交前我还建议你用任意一组小数据把DFS和BFS两份代码都跑一遍输出一致后再提交。这里的价值不在于多花那几十秒而是能在本地就把方向数组、边界判断、标记时机这些最容易出错的地方先过滤一遍能省掉一次罚时。4. 提交后最常踩的坑与排查指南4.1 答案多算或少算八成是方向或标记出了问题第一次做这个题的人最容易出现的状况是代码编译通过样例也过了一提交却Wrong Answer。答案偏大或偏小基本上逃不出几个原因。答案偏大最常见的是八方向漏写。如果你把方向数组写成了四方向只写了上下左右原本通过斜线连通的一大片W就会被分割成多个连通块每次发现剩下的W都会当成新池塘答案自然偏大。另一个原因可能是你把.也当成了访问起点比如遍历主循环时判断条件写成了a[i][j] ! W那每个非池塘的点都会被误判成新池塘。答案偏小常见原因则是标记出了问题。如果DFS递归时没有先把当前格子改成.而是在递归返回后才标记就可能出现两个格子互相递归、或者一个连通块里的不同路径反复访问同一个格子导致部分W被提前跳过。解决方法是进入一个格子时立刻做标记这是Flood fill不变的原则。4.2 递归爆栈、死循环、数组越界我见过一个很典型的Runtime Error原因是数组开小了。题目说n和m最大100你开了a[105][105]开得没问题但如果你用1下标读入而数组恰好只开到a[100][100]那访问a[100][m]时就越界了。建议开数组时多留几个格子的余量比如105乘以105别精确卡着最大范围来。死循环问题主要出现在没标记访问的DFS里。你看代码dfs递归前不执行a[x][y] .那么当从A格子递归到B格子后B格子又会向四个方向搜其中就包括已经走过的A格子于是两个格子来回递归直接栈溢出或者程序超时。还有一种是方向数组不完整造成逻辑死循环概率较低但一旦出现就会非常难排查。如果你用的是BFS也要检查队列是否为pair类型以及入队时标记是否正确。我曾经看到过有人把q.push({nx, ny})放在a[nx][ny] .前面结果同一格被多次重复入队虽然答案偶尔还是对的但复杂度会明显变差数据一大就超时。4.3 一份避坑速查表我把这类题常见的错误场景整理成了一张速查表建议你提交前逐项核对一遍。问题现象可能原因排查与修复方向答案偏大八方向写成四方向或把非W当起点检查dx/dy是否包含8组偏移主循环判断是否严格要求等于W答案偏小标记时机不对重复访问或漏访问进入格子立刻标记不要等出队或回溯时再标记递归栈溢出地图过大、递归层数太深换BFS实现或用循环模拟栈死循环/超时没有访问标记导致来回递归检查是否在每个格子进入时执行了染色Runtime Error数组越界检查边界判断和数组大小建议多开一格余量地图错位scanf读字符时没有处理换行使用cin或scanf( %c)或手动getchar答案差1遍历顺序和计数位置错误检查ans是发生在发现W时而不是在dfs内部4.4 我印象很深的一个调试现场有个学生卡这道题卡了挺久他拿到的输出总是比标准答案大2。我一看代码方向数组是8组没问题边界判断也没问题主循环判断a[i][j] W进入搜索也没问题。后来我让他打印一下每次进入搜索时的坐标发现有一个池塘的起点出现在另一个池塘内部——这就说明他进入搜索前前面那个池塘并没有被完全染色。问题出在他的dfs里他先对8个方向做递归递归返回后才标记原点。你想想这个顺序从起点A搜到邻居B再搜到更深层的CC搜完回溯到BB再回溯到A这时候才把A标记为.。表面上看起来好像没问题可是如果B里的某个邻居刚好是A的另一个邻居DD就会在A被标记之前又发起一次递归搜索把A绕回来一次。虽然大多数时候答案偶然正确但只要地图稍特殊一点就会出现重复计数、答案偏大的情况。修法就是一行改动dfs开头立刻a[x][y] .。这也是我为什么反复强调标记顺序的优先级最高。5. 从1435延伸出去Flood fill的进阶用法5.1 同样的连通块问题用并查集也能解Flood fill不是连通块计数唯一的出路并查集Union-Find是另一个思路。做法是把二维网格中每个格子映射成一个一维编号比如id i * m j。然后从上到下、从左到右扫描每个为W的格子检查它左上、上方、右上、左方这4个“已经处理过”的邻居里有没有W如果有W就Union这两个格子。因为顺序扫描每一对相邻的W只需要考虑它左边和上面的范围就足以覆盖所有连通关系再加上对角线方向的话就是左上、右上再加上左和上相当于单向检查前4个邻居整体复杂度也是O(n乘m)。全部Union完成后统计有多少个W格子的根节点是自己这个数量就是池塘数。并查集实现起来比DFS、BFS略长但它的优势在于处理“不断合并”的动态连通性场景比如地图可能被逐步修改、反复询问连通块数量时Flood fill每次都要重新扫一遍并查集则可以在线维护答案。对于刚学算法的同学这道题用并查集写一遍能加深对连通性建模的理解。5.2 Flood fill的真实应用场景单纯刷题可能感受不到Flood fill的应用价值但它在实际软件里到处都是。图像处理里的连通域分析是最典型的场景Photoshop和Windows画图里的油漆桶工具本质就是Flood fill你点一下某个颜色区域程序会从点击点向外扩散把所有颜色相近的像素全部填充成新颜色。Photoshop里的魔棒选择工具也用到了Flood fill只是判断条件从“颜色相同”变成了“颜色差值在容差范围内”。游戏开发里的寻路和地图生成同样会用到类似逻辑比如扫雷点击空白区域时程序会从点击点向外扩散把所有周围没有地雷的格子全部翻开把游戏地图上大面积的空白区域一次性揭示出来。这也是Flood fill思想的一种变体很多做游戏开发的朋友在写扫雷、地图编辑器时会很有共鸣。从这道OJ题切入你可以把Flood fill理解成一种“图上的种子扩散算法”凡是和区域连接、区域标记、区域填充有关的场景它都是首要考虑的技术方案。5.3 后续刷题路线数池塘的多个变体做完1435一个很自然的进阶方向是把题目条件逐步升级。第一类是改变方向或维数。四方向版本的代表题是“岛屿数量”八方向版本就是今天的数池塘如果再升级成三维空间里的连通块统计比如立体网格里的“水块”数量那方向偏移就从二维的8个方向变成三维的26个方向实现思路完全一致。第二类是从“统计数量”变成“统计额外的度量值”。比如问你最大池塘的面积是多少那你可以在dfs里把计数器带上每访问一个格子就加一搜索结束后对比当前最大值如果问你池塘的周长也只需要在搜索时判断当前格子的四条边是否是边界或旱地围着所有边界格数一遍即可。这些都只需要在原模板上加一点点统计逻辑适合当作练习延伸。第三类是图结构上的变体比如LeetCode上的“被围绕的区域”“太平洋大西洋水流问题”这些题不再单纯统计连通块而是把Flood fill作为前置依赖结合反向搜索、多起点搜索来求答案。做这些题之前把1435这种基础连通块题吃透后面的拓展会顺很多。我个人在实际带训时有个习惯每教一个新算法一定让学生先找一道最基础的模板题把一种主流实现写熟再找两三道变体题去检验掌握程度。1435就是这么一道适合作为Flood fill模板的好题值得你多写几遍尤其是DFS和BFS各提交一次。等你把方向数组、标记时机、边界判断都练到不用多想就能写对的水平后面再遇到同类题目就真的能“一道通、道道通”了。
Flood fill算法入门：八方向数池塘连通块详解（DFS/BFS）
在算法训练里Flood fill 几乎算是一道绕不开的“入门关卡”。东方博宜OJ 1435这道题名字叫“数池塘八方向”题面和农业、水域有关给你一张由字符组成的网格地图W代表水塘.代表旱地让你统计到底有几片池塘。本质上它就是在考连通块计数而连通块计数最经典、最直接的解法就是Flood fill洪泛填充这也是图像处理里“油漆桶”工具背后那套思路。刷过算法题的人都知道这道题难度不高但非常适合用来建立对DFS、BFS和连通性的直觉尤其适合刚接触搜索算法的初学者。我见过不少人把八方向写成四方向、把访问标记漏掉导致死循环甚至因为字符读入的换行问题卡了半天所以今天这篇就把这道题从头到尾拆透。1. 题目拆解数池塘到底在考什么1.1 先读懂题意什么算一个池塘题目输入很简单第一行两个整数n和m表示网格有n行m列。接下来是一个n乘m的字符矩阵矩阵里只有两种字符W表示水坑.表示干地。现在问你整张地图上有多少个池塘。关键不在字符本身而在“池塘”的定义。题目说的池塘是指一块由相邻的W连成的水域一整块W区域算一个池塘。这里“相邻”包含上下左右以及四条对角线也就是说从一个W出发周围一圈8个格子里的W全都跟它是连通的。只要两块W能直接相邻或者通过其他W间接连通它们就算同一个池塘。举个例子如果地图是这样的W.W. .WW. .W..那么第1行第1列的W自己孤零零的算一个池塘而右上角的W和中间一行的两个W、左下方一个W通过八方向连成了一片算另一个池塘。最终答案是2。这个“连成一片的区域算一个”的概念就是连通块。整个题其实就是让你数这张图里有多少个W连通块。1.2 为什么一看到“连通”就该想到Flood fill按名字理解Flood fill就是“洪水填充”。设想一下你往某个水坑倒一桶染料染料会顺着所有连通的W扩散开把整片池塘都染上颜色直到边界为止。这样操作一次你就“消化”掉了一个池塘然后再去找下一个还没被染色的W继续倒染料。每次倒染料代表的都是一个独立池塘倒了几次答案就是几。这是整个算法最核心的思想遍历所有格子只要遇到一个没处理过的W就说明发现了一个新的池塘计数加一然后从它出发把这个W所能到达的所有W全部标记成“已处理”。后续再扫到这些格子时就会直接跳过不会重复计数。把这个思路落到代码上就是最标准的Flood fill。Flood fill之所以是这类连通块题目的首选因为它的实现简单、直观而且时间复杂度和地图规模成线性关系整个图遍历一遍就能统计出所有连通块。相比之下如果你用“数一数有几个W”的朴素思路就完全没法处理“哪些W算同一片池塘”的连通关系答案是必错的。所以看到“连通”“相邻”“一片区域”这类词条件反射就应该是这题用Flood fill。1.3 四方向和八方向差一不注意就丢分“八方向”是这道题最容易翻车的点。很多人在学Flood fill、做岛屿数量类题目时默认都是四方向也就是只走上、下、左、右。比如LeetCode 200“岛屿数量”陆地的连接就是四方向。但东方博宜OJ 1435把条件放宽到了八方向也就是说对角线上的W也算相邻。这一改影响的不是一个判断条件而是整个搜索时的扩展方式。四方向从当前格子出发只能看4个邻居八方向要额外看4个对角线邻居。做搜索时方向数组从4组变成8组漏一组都不行。八方向的方向数组一般这么写int dx[8] {-1, 1, 0, 0, -1, -1, 1, 1}; int dy[8] {0, 0, -1, 1, -1, 1, -1, 1};每一组(dx[i], dy[i])代表一个相对偏移(-1, 0)是上一格(1, 0)是下一格(0, -1)是左一格(0, 1)是右一格剩下的四组正好对应左上、右上、左下、右下四个对角线方向。顺序无所谓但8组必须齐。如果你只写前后左右四个方向提交后答案大概率偏大因为很多本来通过对角线连成一体的池塘会被你拆成好几个。2. 核心实现两种Flood fill写法都要掌握2.1 深度优先DFS版本代码最短适合入门Flood fill最直观的写法是DFS也就是递归地往外扩展。从一个W格子出发递归地去访问它周围的8个邻居邻居如果是W就继续递归直到没有可扩展的邻居为止。DFS的完整代码如下#include iostream using namespace std; int n, m, ans; char a[105][105]; 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) { a[x][y] .; // 访问过就把W改成.相当于染色标记 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 a[nx][ny] W) { dfs(nx, ny); } } } int main() { cin n m; for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j]; } } for (int i 0; i n; i) { for (int j 0; j m; j) { if (a[i][j] W) { ans; dfs(i, j); } } } cout ans endl; return 0; }这套代码里有个很聪明的细节不需要额外开一个二维vis数组来标记哪些格子访问过而是直接把访问过的W改成.。反正这个格子已经属于当前正在统计的池塘之后无论从哪个入口进入搜索它都不会再被当作新池塘的起点。这种“原地染色”的技巧能节省内存也让代码更简洁。在dfs函数内部边界判断必须写在访问数组之前。原因很简单如果不先判断nx和ny是否越界直接去访问a[nx][ny]那么当坐标越界时就会读到数组外的垃圾数据轻则逻辑混乱重则直接Runtime Error。常见的写法就是先用四个布尔表达式把边界卡住确保只有合法坐标才进入下一步判断。2.2 广度优先BFS版本更稳不怕递归爆炸DFS简洁但不是没有代价。递归调用会占用系统栈空间如果一张地图特别大或者有一片巨大的W区域递归深度可能非常深深到把系统栈撑爆程序直接崩溃。这时候BFS的队列实现就体现出优势了BFS用队列保存待扩展的格子一层一层向外扩完全不依赖递归也就不存在栈溢出问题。BFS版本的代码如下#include iostream #include queue using namespace std; int n, m, ans; char a[105][105]; int dx[8] {-1, 1, 0, 0, -1, -1, 1, 1}; int dy[8] {0, 0, -1, 1, -1, 1, -1, 1}; void bfs(int x, int y) { queuepairint, int q; q.push({x, y}); a[x][y] .; while (!q.empty()) { auto cur q.front(); q.pop(); for (int i 0; i 8; i) { int nx cur.first dx[i]; int ny cur.second dy[i]; if (nx 0 nx n ny 0 ny m a[nx][ny] W) { a[nx][ny] .; q.push({nx, ny}); } } } } int main() { cin n m; for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j]; } } for (int i 0; i n; i) { for (int j 0; j m; j) { if (a[i][j] W) { ans; bfs(i, j); } } } cout ans endl; return 0; }注意BFS里的一个细节每当一个格子满足条件被加入到队列时就立刻把它改成.而不是等它出队时再改。这个顺序很关键。如果等到出队才标记同一个格子可能被多个邻居重复入队队列里会出现大量冗余节点在某些连通性很强的图里会白白增加好几倍的运算量。入队即标记是BFS处理二维网格的经典优化也是我经常强调的“入队时染色”原则。2.3 DFS和BFS怎么选从数据规模出发我给学生讲这道题时每次都会让他们把DFS和BFS各写一遍因为两种思路各有适用场景。从时间复杂度的角度看DFS和BFS完全一样都是O(n乘m)因为每个格子最多被入队或者递归访问一次。空间复杂度上的差异主要体现在“单次搜索撑开的规模”DFS依赖递归栈栈深等于当前连通块中从起点到最远点的递归路径长度BFS依赖队列队列最长的时候往往出现在地图有一片特别宽大的连通区域时。在极端情况下比如一张2000乘2000的图全是WDFS的递归深度可能会达到几十万层这在很多评测环境下已经非常危险而BFS队列存储的节点数量最多也就是地图总格数也就是400万左右通常可控。东方博宜OJ 1435的数据范围我记得n和m都不会太大用DFS完全没问题。但如果平时训练想培养稳妥的做题习惯建议小数据用DFS快速验证思路正式处理规模不确定的题时优先选择BFS。尤其是在面试或竞赛中栈溢出是Runtime Error里最让人头疼的一种而BFS能帮你彻底避开这个雷区。3. 逐行拆解提交过程与关键细节3.1 字符地图的读入cin、scanf与换行符很多刚接触字符矩阵的人会在读入上翻车。先说你用cin读字符的情况cin有一个特性它会自动跳过空白字符包括空格、换行符和制表符。所以这种代码for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j]; } }是可以正确工作的。第一行的n和m读完剩下的换行符会被cin自动跳过接着读到的第一个字符就是地图第一行的第一个字符中间哪怕有换行也不会被读进数组里。但如果用的是scanf配合%c读单个字符问题就来了。%c不会自动跳过任何空白字符你把上一行的换行符留在了输入缓冲区下一句scanf(%c, a[i][j])读到的就会是那个换行符整个地图数据全部错位。这种错的表现为你一输出整个地图第一列全是莫名其妙的空白或者答案出现明显的偏差。用scanf读字符矩阵时要么在%d后面手动吃一次getchar()要么用scanf( %c, a[i][j])——注意%c前面加一个空格让scanf先跳过空白字符再读。这也是我平时更推荐cin读字符的原因代码更简洁还少踩一类坑。3.2 坐标从0还是从1两种习惯的边界判断我前面给的代码用的是0下标也就是数组从a[0][0]开始读边界判断写成nx 0 nx n。这种写法符合C数组的原生形态写起来麻烦一点点但不容易搞错下标。另一种常见做法是用1下标也就是从a[1][1]开始存整个地图外围留一圈空边界这圈边界初始值是\0或.都无所谓因为搜索时只需关注实际地图范围。用1下标时读入循环是这样的for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; } }边界判断则简化成nx 1 nx n ny 1 ny m。1下标的好处在于它和日常坐标习惯一致第1行第1列就是地图左上角不容易在坐标换算上头晕。两种写法都能过但我个人建议初学者固定用其中一种反复多练几道题直到形成肌肉记忆省得每次写题都在边界判断上犹豫。无论是0下标还是1下标方向数组都是一样的。真正容易写错的是循环里的j是不是从0开始、m和n哪个对应行哪个对应列。先把n当作行数、m当作列数方向变化只在一二维坐标上做算术思路会清晰很多。3.3 自造样例验证手动模拟一遍Flood fill拿到这种题跑通代码之前先自己手算一遍样例非常有必要。我给你一个自造的简单用例3 4 W.W. .WW. W...手动模拟一遍第一步从第0行第0列开始扫发现a[0][0]是Wans变成1进入dfs。 从这个格子出发可以到达8个邻居中所有的W。第0行第2列是W第1行第1列是W第1行第2列也是W。继续向下扩展后第2行第0列的W也会被访问到。整个过程中所有被dfs染成.的格子组成了第一个池塘。继续扫描整张图剩下的格子全部是.没有新的W出现所以最终ans1。你也许会想右上角那个W和左下角那个W不是离得很远吗但是它们通过中间交叉的斜线连成了一个整体这正是八方向搜索的意义所在。如果这个题改成四方向那这几个W就会被拆成两个甚至三个池塘答案就完全不一样了。提交前我还建议你用任意一组小数据把DFS和BFS两份代码都跑一遍输出一致后再提交。这里的价值不在于多花那几十秒而是能在本地就把方向数组、边界判断、标记时机这些最容易出错的地方先过滤一遍能省掉一次罚时。4. 提交后最常踩的坑与排查指南4.1 答案多算或少算八成是方向或标记出了问题第一次做这个题的人最容易出现的状况是代码编译通过样例也过了一提交却Wrong Answer。答案偏大或偏小基本上逃不出几个原因。答案偏大最常见的是八方向漏写。如果你把方向数组写成了四方向只写了上下左右原本通过斜线连通的一大片W就会被分割成多个连通块每次发现剩下的W都会当成新池塘答案自然偏大。另一个原因可能是你把.也当成了访问起点比如遍历主循环时判断条件写成了a[i][j] ! W那每个非池塘的点都会被误判成新池塘。答案偏小常见原因则是标记出了问题。如果DFS递归时没有先把当前格子改成.而是在递归返回后才标记就可能出现两个格子互相递归、或者一个连通块里的不同路径反复访问同一个格子导致部分W被提前跳过。解决方法是进入一个格子时立刻做标记这是Flood fill不变的原则。4.2 递归爆栈、死循环、数组越界我见过一个很典型的Runtime Error原因是数组开小了。题目说n和m最大100你开了a[105][105]开得没问题但如果你用1下标读入而数组恰好只开到a[100][100]那访问a[100][m]时就越界了。建议开数组时多留几个格子的余量比如105乘以105别精确卡着最大范围来。死循环问题主要出现在没标记访问的DFS里。你看代码dfs递归前不执行a[x][y] .那么当从A格子递归到B格子后B格子又会向四个方向搜其中就包括已经走过的A格子于是两个格子来回递归直接栈溢出或者程序超时。还有一种是方向数组不完整造成逻辑死循环概率较低但一旦出现就会非常难排查。如果你用的是BFS也要检查队列是否为pair类型以及入队时标记是否正确。我曾经看到过有人把q.push({nx, ny})放在a[nx][ny] .前面结果同一格被多次重复入队虽然答案偶尔还是对的但复杂度会明显变差数据一大就超时。4.3 一份避坑速查表我把这类题常见的错误场景整理成了一张速查表建议你提交前逐项核对一遍。问题现象可能原因排查与修复方向答案偏大八方向写成四方向或把非W当起点检查dx/dy是否包含8组偏移主循环判断是否严格要求等于W答案偏小标记时机不对重复访问或漏访问进入格子立刻标记不要等出队或回溯时再标记递归栈溢出地图过大、递归层数太深换BFS实现或用循环模拟栈死循环/超时没有访问标记导致来回递归检查是否在每个格子进入时执行了染色Runtime Error数组越界检查边界判断和数组大小建议多开一格余量地图错位scanf读字符时没有处理换行使用cin或scanf( %c)或手动getchar答案差1遍历顺序和计数位置错误检查ans是发生在发现W时而不是在dfs内部4.4 我印象很深的一个调试现场有个学生卡这道题卡了挺久他拿到的输出总是比标准答案大2。我一看代码方向数组是8组没问题边界判断也没问题主循环判断a[i][j] W进入搜索也没问题。后来我让他打印一下每次进入搜索时的坐标发现有一个池塘的起点出现在另一个池塘内部——这就说明他进入搜索前前面那个池塘并没有被完全染色。问题出在他的dfs里他先对8个方向做递归递归返回后才标记原点。你想想这个顺序从起点A搜到邻居B再搜到更深层的CC搜完回溯到BB再回溯到A这时候才把A标记为.。表面上看起来好像没问题可是如果B里的某个邻居刚好是A的另一个邻居DD就会在A被标记之前又发起一次递归搜索把A绕回来一次。虽然大多数时候答案偶然正确但只要地图稍特殊一点就会出现重复计数、答案偏大的情况。修法就是一行改动dfs开头立刻a[x][y] .。这也是我为什么反复强调标记顺序的优先级最高。5. 从1435延伸出去Flood fill的进阶用法5.1 同样的连通块问题用并查集也能解Flood fill不是连通块计数唯一的出路并查集Union-Find是另一个思路。做法是把二维网格中每个格子映射成一个一维编号比如id i * m j。然后从上到下、从左到右扫描每个为W的格子检查它左上、上方、右上、左方这4个“已经处理过”的邻居里有没有W如果有W就Union这两个格子。因为顺序扫描每一对相邻的W只需要考虑它左边和上面的范围就足以覆盖所有连通关系再加上对角线方向的话就是左上、右上再加上左和上相当于单向检查前4个邻居整体复杂度也是O(n乘m)。全部Union完成后统计有多少个W格子的根节点是自己这个数量就是池塘数。并查集实现起来比DFS、BFS略长但它的优势在于处理“不断合并”的动态连通性场景比如地图可能被逐步修改、反复询问连通块数量时Flood fill每次都要重新扫一遍并查集则可以在线维护答案。对于刚学算法的同学这道题用并查集写一遍能加深对连通性建模的理解。5.2 Flood fill的真实应用场景单纯刷题可能感受不到Flood fill的应用价值但它在实际软件里到处都是。图像处理里的连通域分析是最典型的场景Photoshop和Windows画图里的油漆桶工具本质就是Flood fill你点一下某个颜色区域程序会从点击点向外扩散把所有颜色相近的像素全部填充成新颜色。Photoshop里的魔棒选择工具也用到了Flood fill只是判断条件从“颜色相同”变成了“颜色差值在容差范围内”。游戏开发里的寻路和地图生成同样会用到类似逻辑比如扫雷点击空白区域时程序会从点击点向外扩散把所有周围没有地雷的格子全部翻开把游戏地图上大面积的空白区域一次性揭示出来。这也是Flood fill思想的一种变体很多做游戏开发的朋友在写扫雷、地图编辑器时会很有共鸣。从这道OJ题切入你可以把Flood fill理解成一种“图上的种子扩散算法”凡是和区域连接、区域标记、区域填充有关的场景它都是首要考虑的技术方案。5.3 后续刷题路线数池塘的多个变体做完1435一个很自然的进阶方向是把题目条件逐步升级。第一类是改变方向或维数。四方向版本的代表题是“岛屿数量”八方向版本就是今天的数池塘如果再升级成三维空间里的连通块统计比如立体网格里的“水块”数量那方向偏移就从二维的8个方向变成三维的26个方向实现思路完全一致。第二类是从“统计数量”变成“统计额外的度量值”。比如问你最大池塘的面积是多少那你可以在dfs里把计数器带上每访问一个格子就加一搜索结束后对比当前最大值如果问你池塘的周长也只需要在搜索时判断当前格子的四条边是否是边界或旱地围着所有边界格数一遍即可。这些都只需要在原模板上加一点点统计逻辑适合当作练习延伸。第三类是图结构上的变体比如LeetCode上的“被围绕的区域”“太平洋大西洋水流问题”这些题不再单纯统计连通块而是把Flood fill作为前置依赖结合反向搜索、多起点搜索来求答案。做这些题之前把1435这种基础连通块题吃透后面的拓展会顺很多。我个人在实际带训时有个习惯每教一个新算法一定让学生先找一道最基础的模板题把一种主流实现写熟再找两三道变体题去检验掌握程度。1435就是这么一道适合作为Flood fill模板的好题值得你多写几遍尤其是DFS和BFS各提交一次。等你把方向数组、标记时机、边界判断都练到不用多想就能写对的水平后面再遇到同类题目就真的能“一道通、道道通”了。