我最近在整理算法模板的时候又把编号 1097 的池塘计数翻出来重写了一遍。这道题可以说是 C 学习 FloodFill 算法最经典的入门题一块 n×m 的地图格子要么是水W要么是干地.只要八个方向之一能被水连起来就算同一片池塘。整个程序写下来不过几十行但里面藏着的「八连通」「字符串读入」「用 BFS 还是 DFS」这几个细节恰恰是很多初学者第一次做时卡住的地方。这篇文章就把完整的解题思路、可提交的 C 代码、以及我自己实测过的几个大坑都整理出来给刚接触 FloodFill、或者准备算法面试的同学做个参考。1. “池塘”的判定规则八连通、字符串读入与连通块计数1.1 先搞清楚什么算同一片池塘题目描述通常很简单一个 n 行 m 列的矩阵每格是字符W或.。W代表积水.代表干燥地面。池塘的定义是「连在一起的 W 的集合」这里的连在一起并不是只看上下左右而是把左上、右上、左下、右下四个斜角也算进来。八个方向任意一个方向相邻两个水格就属于同一片池塘。我最早做的时候其实没细想什么叫「相连」只写了上下左右四个方向结果样例过得很顺利一交上去答案就比预期大了。原因很简单同一片池塘里斜对角的两块水在四连通规则下被拆成了两块计数自然变多。所以拿到题第一步不是写代码而是确定连通规则。连通方式方向数量包含方向斜角相邻是否算连通四连通4上、下、左、右否八连通8上、下、左、右、左上、右上、左下、右下是这道「池塘计数」用的是八连通也就是八个方向都要检查。一个很典型的例子是W . . W四连通规则下右上角的 W 和左下角的 W 并不相邻算两片池塘但八连通规则下它们通过斜对角直接相连只算一片池塘。这个例子我建议第一次做的人亲自跑一遍能帮你立刻确认自己对连通规则的理解有没有问题。1.2 输入格式的坑一行字符串里有换行符题目多数版本的输入格式是第一行两个整数 n、m接下来 n 行每行一个长度为 m 的字符串比如W..W中间没有空格。正因为没有空格最省事的做法就是cin n m; for (int i 0; i n; i) cin g[i];这里g[i]是一个char数组cin g[i]会直接跳过换行符把一整行字符串读进来非常干净。但如果你习惯用scanf(%c)按字符读就会踩到一个很隐蔽的坑%c不会跳过换行符每一行的末尾那个\n会被当成一个独立字符读进来。这会导致地图行错位或者多出一堆奇怪的判定。以前有的同学用scanf(%s, g[i])其实也是可以的因为%s会自动跳过空白字符但如果你在字符之间加了空格%s又会只读到空格为止又会出现另一类问题。所以我的建议是能用cin 字符串就用它简单直接不给自己留读入的坑。另一个容易忽略的点是地图的字符串里只有字符W和.没有数字。如果你在判断里写成if (g[nx][ny] W)就不会判错但如果把W的字符编码记错或者把输入当数字读那后面一切判断全是错的。这种低级错误最好在写代码前就通过打印输入规避掉。1.3 连通块算法题里的“数有几片”「池塘计数」本质上问的是地图上有多少个连通块。什么叫连通块你可以把所有为W的格子想象成一张渔网上的节点两个节点如果八方向相邻就说明它们之间有一根线连着。一张图会被若干根线分成若干坨「连在一起的节点组」每一坨就是一个连通块。FloodFill 算法做的事情和「往一个连通块里灌水让它全部变色」是一模一样的。从一个起点开始不断向它周围相邻、且没被访问过的水格扩散直到这一片区域全被染色。染完这一片再去扫描下一个还没被染色的水格就说明发现了新的一片池塘。这就是为什么 FloodFill 天然适合连通块计数。这个思路也为整个程序的框架定了调外层两个for循环扫描整张地图遇到没访问过的W就把答案加一然后用 FloodFill 把这个W所在的整片池塘全部标记掉。下一次扫描到这片池塘里的任何格子时因为它们已经被标记过不会再触发计数。2. FloodFill 核心思路拆解一次填充干掉一片池塘2.1 外层扫描 内层填充的分工接触 FloodFill 时最容易犯的错是想在一个for循环里同时完成「扩散」和「计数」。其实这两个任务完全可以分开来外层扫描遍历每个格子判断它是不是一个「新的池塘起点」。内层填充从起点出发把整片池塘的所有格子全部标记为已访问。核心判断就一行if (g[i][j] W !vis[i][j]) { ans; bfs(i, j); }这里的ans代表我遇到了一个之前完全没见过的水格它所在的池塘还没被处理过所以这是一片新池塘。然后调bfs把这整片都处理完后面再扫描到这片池塘里的其他格子它们已经被vis标记了不会再触发ans。这个模式可以说是 FloodFill 的骨架理解它比背代码重要得多。我后来做很多地图类题目比如「岛屿数量」「被包围的区域」「最大人工岛」外层扫描 内层扩散的框架完全一致只是填充函数内部处理的东西不同。2.2 入队即标记细节决定性能上限写 BFS 的时候有一个细节经常被忽略一个格子应该在「入队的时候」标记为已访问还是「出队的时候」标记正确答案是入队时标记。原因很简单如果你只在出队时标记那么同一个格子可能被它的多个邻居先后加入队列。比如说某个格子左上方的邻居先把它放进队列了结果它右侧的邻居在出队时又检查到它还没标记又把它放了一次队列。在二叉树或无环图上可能影响不大但在网格图里每个格子最多有 8 个邻居一个格子被重复入队 8 次的情况是真实存在的。整个地图全是水时队列长度会不断膨胀时间和空间都会浪费。用一句话记住入队时标记出队时不用管标记。我在本地用 1000×1000 的全W地图测试过入队时标记的版本很稳定地跑完如果改成出队时标记运行时间明显变长极端情况下队列里会有大量重复元素内存也涨得让人不安。2.3 DFS 和 BFS 的取舍为什么推荐 BFSFloodFill 有两种常见实现方式——DFS深度优先和 BFS广度优先。DFS 版本非常短核心就是一个递归函数void dfs(int x, int y) { g[x][y] .; for (int i 0; i 8; i) { int nx x dx[i], ny y dy[i]; if (nx 0 || nx n || ny 0 || ny m) continue; if (g[nx][ny] W) dfs(nx, ny); } }看起来舒服但有一个致命问题递归深度。如果整张地图 1000×1000 全是W从左上角开始 DFS它会沿着一条蛇形路径一路递归到底递归深度可能达到一百万层。很多程序的默认栈空间是撑不住这种深度的跑起来直接段错误。所以我的建议很明确在 OJ 上做这道题默认用 BFS 队列版本。BFS 用的队列是堆内存不会因为递归深度爆栈代码量也只多几行非常划算。并不是说 DFS 不能做这道题而是你的程序要在不可控的测试环境下保证不崩BFS 是最稳的选择。3. 可提交的 C BFS 完整代码与方向数组写法3.1 完整可运行版本下面这份代码我加了详细的注释直接照着理解就能跑通#include bits/stdc.h using namespace std; const int N 1010; int n, m; char g[N][N]; bool vis[N][N]; // 八方向的 x 和 y 偏移顺序从左上一圈到右下 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 (g[nx][ny] ! W || vis[nx][ny]) continue; vis[nx][ny] true; q.push({nx, ny}); } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for (int i 0; i n; i) cin g[i]; int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (g[i][j] W !vis[i][j]) { ans; // 发现新池塘 bfs(i, j); // 淹掉整片池塘 } } } cout ans \n; return 0; }这份代码的细节上面都讲过了唯一要注意的是全局数组的大小。const int N 1010用来应对最大 1000×1000 的地图留了一点余量。如果你看到题目的范围是 2000 或更大记得把 N 改到对应大小至少要比范围上限再大 10防止边界处的数组越界访问。3.2 方向数组的两种等价写法显式列出 8 个方向的偏移量是最直观的写法但这要求你把每个偏移量想清楚。另一种不容易漏方向的写法是用双层循环枚举相对偏移量for (int i -1; i 1; i) { for (int j -1; j 1; j) { if (i 0 j 0) continue; // 跳过原地 int nx x i; int ny y j; // 后续检查照旧 } }这种写法的好处是天然覆盖了八个方向不会因为手滑漏掉某个斜角。如果你的地图很大显式写 8 项方向数组在常数上反而更高效因为少了一层if判断。但对初学者来说双层循环更不容易出错。我自己的习惯是能用显式方向数组就用显式但必须在心里默念「上、右上、右、右下、下、左下、左、左上」八个方向逐项核对一遍。3.3 手推一遍 3×3 样例理解队列扩散假设地图是W W . W . . . . .从(0,0)开始发现是没访问过的W计数变成 1然后进入 BFS。起始(0,0)入队并标记弹出后检查八个邻居(0,1)和(1,0)都是W且未访问依次入队。弹出(0,1)它的邻居里(1,0)已经被标记不会重复入队。弹出(1,0)检查一圈没有新的W。队列为空这整个过程代表一片池塘被完全处理。外层继续扫描走到(0,1)时发现vis已标记直接跳过走到(1,0)同理。最终答案就是 1。这个过程看着简单却很能说明 BFS 的扩散顺序从起点一圈一圈地往外扩展像水波一样。4. 实测表现复盘全 W 大矩阵下的段错误与三个老坑4.1 1000×1000 全 WDFS 递归直接崩我在本地做了一次对比测试生成一张 1000×1000、全部是W的地图分别跑 BFS 版本和递归 DFS 版本。BFS 版本在开-O2的情况下跑得很快输出结果 1符合预期。递归 DFS 版本就惨了程序一跑起来就段错误。原因不是算法错而是递归深度直接冲到了接近一百万层默认栈空间扛不住。这个现象非常直观地说明了为什么我推荐 BFS不是 DFS 不够优雅而是它在这种极端数据下不够稳。如果你真的想用 DFS 的思路去做也不是完全没救可以改成手动栈模拟递归但代码复杂度会明显上升性价比不高。既然 BFS 的代码也就多了几行何必给自己找麻烦。4.2 坑一方向数组漏掉斜对角这是典型的「样例全对、提交报错」案例。如果方向数组只写了上下左右四个方向int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1};那么前面说的W ./. W这种情况就会判定为两个池塘答案偏大。题目要求八连通你却用了四连通等于换了一道题。排查方法我前面也提过把方向数组的每一项按方位写成注释逐一和题目的连通规则对照。这个习惯我到现在都保留着尤其是写地图类题目时方向数组永远是我提交前必查的第一项。4.3 坑二越界判断只写了半边八个方向的坐标偏移可能让nx或ny变成负数也可能超过 n 或 m 的范围。很多同学会写if (nx n ny m nx 0 ny 0) continue;然后发现数组访问越界或者行为诡异。其实这四种条件的顺序不重要重要的是你有没有把四个条件全想到。写成下面的形式更稳妥if (nx 0 || nx n || ny 0 || ny m) continue;用「越界就跳过」的负向判断把所有非法情况一次性拦截掉逻辑上更清晰也不容易漏。这是我在代码里一直用的风格。4.4 坑三字符读入把换行符算进去了如果你用scanf(%c)循环读字符每读完一行末尾的\n都会留在输入流里下一次%c就会把这个换行符读进地图。肉眼看不出来但程序里的地图行数会错乱判断W时那些换行符自然全是假的。这里我直接建议如果你用 C就尽量让cin去读字符串别跟%c较劲。如果题目给的输入是像W W .这样带空格的单字符序列那就用char ch; cin ch;读取cin会自动跳过空格和换行。4.5 一个小排查表现象可能原因修复方法答案偏大样例能过但大数据错方向数组少了斜对角方向检查八方向偏移量是否齐全程序运行异常或段错误越界判断漏掉负数递归 DFS 深度过大补全四个边界条件改用 BFS地图读入后错位%c读入了换行符改用cin g[i]读整行队列队头永久取不完出队时才标记重复入队改成入队时立即标记5. 一道模板题的三种延伸从池塘到岛屿到最大面积5.1 四连通版本把 8 个方向改成 4 个方向很多面试题喜欢把「池塘计数」改成四连通版本典型代表就是「岛屿数量」给你一个0/1网格1 表示陆地0 表示水求岛屿数量。这道题的连通规则是四连通也就是只考虑上下左右四个方向。改法非常简单把方向数组换成int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1};其他逻辑完全不变。这就是 FloodFill 模板的优势规则一变只需要动一个数组剩下的框架不用碰。我第一次做岛屿数量题时几乎就是照搬池塘计数的代码只是把字符从W换成了1方向从八个换成四个。省下来的时间都拿来想题目本身的边界条件了。所以不要觉得池塘计数太小看不上它其实是很多连通性题目的母题。你把它吃透相当于把一整个题型的套路记住了。5.2 从「有几个池塘」到「最大的池塘有多大」如果题目改成「求最大的池塘面积」BFS 也不难扩展。你只需要让 BFS 返回它填了多少个格子然后在主函数里维护一个最大值int bfs(int sx, int sy) { int cnt 0; queuepairint, int q; q.push({sx, sy}); vis[sx][sy] true; while (!q.empty()) { auto [x, y] q.front(); q.pop(); cnt; 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 (g[nx][ny] ! W || vis[nx][ny]) continue; vis[nx][ny] true; q.push({nx, ny}); } } return cnt; }外层循环里把原来的ans改成int area bfs(i, j); maxArea max(maxArea, area);这就是连通块最大面积的通用写法。类似的还可以统计每个池塘的周长、被包围区域的大小等等核心永远是「填充的时候顺便统计你需要的信息」。5.3 多源 FloodFill把多个起点同时塞进队列有时候地图上会有多个出发点比如很多个火源同时蔓延题目要你求整个区域被覆盖的时间。这时候不需要把外层循环里的每个起点分别跑一遍 BFS而是可以把所有起点先全部放进同一个队列然后做 BFS。这种「多源 BFS」本质上还是 FloodFill只是初始状态从单点变成了多点。核心原因在于 BFS 的队列天然可以容纳多个起始节点扩散顺序依然是按层推进先覆盖距离为 1 的点再覆盖距离为 2 的点。理解了这一点很多「从多个点同时扩散」的场景都能直接套模板。我在做图像处理的「种子填充」算法时也有类似的感受Photoshop 里的油漆桶工具本质上就是对某个区域做 FloodFill把它换成另一种颜色。算法课上学到的这个东西远不止 OJ 上的模板题这么简单。最后再分享一个我自己的习惯每次写完地图类的 FloodFill 题目我都会在提交前盯着方向数组和标记位置看十秒钟。方向数组有没有漏是入队标记吗越界条件四个方向都写了吗这三个问题问完基本不会因为基础细节翻车。这道池塘计数虽然简单但它逼着我养成了这套检查习惯后来的很多地图题里我都靠这个习惯省下了大把调试时间。