如果你刚接触算法竞赛第一次看到“求细胞数量”这几个字多半会以为这题和生物有关。洛谷P1451 求细胞数量实际上是一道非常经典的二维网格连通块计数问题——给你一张由数字组成的矩阵0 表示空白非 0 表示细胞上下左右连通的非 0 区域算一个细胞最后输出一共有多少个细胞。我第一次做这道题时一度以为是数学题想在纸上硬数后来才发现它真正想教你的是 BFS 和 DFS 里的连通块遍历也叫 flood fill洪水填充。这篇不是单纯丢一段 AC 代码而是把这题的建模方式、遍历思路、两套完整写法、常见坑位和背后的实际应用全部拆开讲一遍适合准备入门搜索算法、或者刚刷完基础题想找题感的朋友。1. “求细胞数量”到底在考什么一上来先看模型1.1 把题目翻译成人话题目描述并不复杂给定 m 行 n 列的矩形网格网格里每个位置是一个数字字符。数字 0 表示空白区域非 0 数字表示细胞。所谓“同一个细胞”是指上下左右方向直接相邻的一片非 0 区域。注意斜对角方向不算相邻。最终要回答这片矩阵里一共有多少个独立的细胞群。举个例子一个 3×3 的矩阵0 1 0 1 2 0 0 0 3第一行第二列的 1和下面第二行第一列的 1虽然在位置上斜着错开但它们是上下左右相邻吗不是它们中间隔着一个 0所以“1”和“1”不算同一个细胞。而第一行第二列的 1 与第二行第二列的 2 上下相邻它们属于同一块区域构成第一个细胞。右下角的 3 孤零零四周都是 0算第二个细胞。答案就是 2。为什么不能靠人眼数因为矩阵最大能到 100×100稍微大一点肉眼就会漏。算法要解决的问题是把“看起来连在一起”这种模糊感觉变成一条明确的规则遍历所有格子凡是没访问过的非 0 格子就把和它连通的一整片全部标记计数器加一。1.2 这题的真正身份二维网格上的连通分量从图论的角度看题目的本质很容易拆穿。把每个格子当作一个节点两个格子上下左右相邻且都不是 0就认为它们之间存在一条边。那么整张矩阵就变成了一个无向图“细胞”就是图中的一个连通分量。统计细胞数量等于统计连通分量数量。这也是为什么学完这道题之后再去看“岛屿数量”“油田块数”“传染扩散”之类的题目会觉得换汤不换药——它们全都在考同一套能力在一块网格上用搜索算法把彼此连通的区域整体圈出来。图像处理里有一个专门的说法叫连通区域标记英文缩写 CCL二值图像里统计目标区域数量用的就是这套思路。所以不要觉得这只是一道新手题它是很多实际算法的基础模板。2. 核心思路拆解扫描、标记、扩散三件事2.1 一次圈一块地外层扫描和内层扩散的分工理解了模型之后算法流程就非常清晰了。可以概括成三个动作扫描、标记、扩散。全局扫描是外层循环负责在整张矩阵里寻找“新细胞”的起点扩散是内层搜索负责把一个起点所在的整个连通块全部走完。具体步骤如下从左到右、从上到下扫描每个格子。遇到非 0 数字且这个格子没有被访问过说明发现了一个新的细胞计数器加一。以这个格子为起点进行 BFS 或 DFS把和它上下左右相连的非 0 格子全部找出来并逐个标记成“已访问”。扩散结束后这个细胞的所有格子都已经被标记外层扫描继续往后走。最终计数器里的数值就是答案。为什么顺序扫描不会漏掉某个细胞这里有一个很朴素的道理任何一个连通块只要它里面有格子那么按顺序逐格扫描时总有一个格子是这个连通块中“第一次被扫到的那个”。无论从哪个位置进入以它为起点开始扩散整块区域都会被覆盖到。扩散完成后所有格子打了标记后面再遇到它们就会自动跳过。所以外层扫描只需要负责“发现第一块拼图”剩下的交给扩散。2.2 访问标记为什么是生命线不标记会怎样如果你第一次写这类代码最容易忽略的就是“标记已访问”这步。我在给某些朋友讲这道题的时候有人说我在扩散时把相邻格子入队不就好了吗为什么要多写一个标记问题在于如果不标记队列里的格子会互相重复入队。拿一个 2×2 全是非 0 的矩阵模拟一下1 1 1 1假设从左上角开始 BFS先把左上角入队。弹出左上角后检查它的下方和右方于是右下不是是它的正下方和正右方入队。处理正下方时它又会发现上方这个格子已经是队列里处理过的但因为没有标记它会再次把左上角入队。处理正右方时同样的事情再次发生。结果就是格子被反复加入队列程序陷入无限循环。标记的作用可以理解成“圈地打桩”每块地一旦被圈过就在边界插一根旗子后面任何人看到旗子都知道这里已经处理完了不能再进。对本题来说标记有两种常见方案开一个 bool vis[105][105]访问过就置为 true。直接把原矩阵里的非 0 字符改成 0相当于原地标记。第二种方案在这道题里特别好用因为统计完成后我们不再需要原始数据原地置零既省内存又省代码。我后面给出的完整代码就采用这种写法。2.3 方向数组用一份“上下左右”模板走遍全图遍历相邻格子时最笨的写法是写四段 if 分别判断上、下、左、右。这样写也不是不行但代码会变得又长又容易漏。比较推荐的做法是维护两个方向数组把四个方向的坐标变化统一处理方向dxdy上-10下10左0-1右01于是从当前格子 (x, y) 出发新的格子坐标就是 (x dx[i], y dy[i])。配合一个 for 循环四次方向判断就全部覆盖了。边界条件也要在这个循环里一起判断防止下标越界。如果你以后遇到“八连通”的题目比如斜对角也算相邻只需要把方向数组扩成 8 个分量dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; dy[8] {-1, 0, 1, -1, 1, -1, 0, 1};搜索的核心代码一行都不用改。这就是方向数组的价值把“怎么走”和“走到哪去”彻底分离开。3. 两种 AC 写法BFS 队列版与 DFS 递归版的完整实现3.1 BFS 队列版最推荐新手吃透的写法先给出 BFS 的完整 C 代码。代码里使用 queue 作为扩散容器用原地标记的方式避免额外开 vis 数组。#include bits/stdc.h using namespace std; const int MAXN 105; char grid[MAXN][MAXN]; int m, n; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; void bfs(int sx, int sy) { queuepairint, int q; q.push(make_pair(sx, sy)); grid[sx][sy] 0; // 入队前就标记防止重复入队 while (!q.empty()) { int x q.front().first; int y q.front().second; q.pop(); for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 || nx m || ny 0 || ny n) continue; if (grid[nx][ny] 0) continue; grid[nx][ny] 0; // 同样在入队时标记 q.push(make_pair(nx, ny)); } } } int main() { scanf(%d%d, m, n); for (int i 0; i m; i) { scanf(%s, grid[i]); } int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] ! 0) { ans; bfs(i, j); } } } printf(%d\n, ans); return 0; }代码里有几个细节值得说明。首先每次把新格子 push 进队列之前就立刻把字符改成 0这个动作非常关键。为什么不是弹出队列的时候再标记因为从入队到出队之间可能隔着很长时间如果一个格子先被某个邻居发现并入队还没轮到弹出时又被另一个邻居发现如果没有提前标记它就会被重复入队。提前标记相当于在入队那一刻就打上“已被接管”的标签从源头杜绝重复。其次pairint, int 用来存坐标写法简单但如果你对性能有要求或者想更清晰可以自己定义一个 struct Node。另外外层循环扫描时只要发现 grid[i][j] ! 0就说明这里是某个新细胞的起点。因为所有已经被处理过的格子都变成了 0所以不需要再判断访问状态。3.2 DFS 递归版代码更短但要注意递归深度DFS 递归版和 BFS 的核心区别只在于扩散时使用的容器BFS 用队列DFS 用函数调用栈。下面是完整代码。#include bits/stdc.h using namespace std; const int MAXN 105; char grid[MAXN][MAXN]; int m, n; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; void dfs(int x, int y) { grid[x][y] 0; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 || nx m || ny 0 || ny n) continue; if (grid[nx][ny] 0) continue; dfs(nx, ny); } } int main() { scanf(%d%d, m, n); for (int i 0; i m; i) { scanf(%s, grid[i]); } int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] ! 0) { ans; dfs(i, j); } } } printf(%d\n, ans); return 0; }DFS 的代码在行数上比 BFS 更短因为它不需要显式声明队列递归本身就在维护一个栈。对于 P1451 这种 100×100 规模的数据递归深度最多也不会超过 10000完全在默认栈空间的可接受范围内可以放心提交。但如果你以后做更大规模的地图题比如 1000×1000 的网格里出现了一条蛇形弯曲的连通块递归深度可能达到几十万层这时很容易出现栈溢出程序直接报 Segmentation Fault。这种时候两种兜底方案一是改用 BFS彻底避开递归调用栈二是把队列换成栈容器写成显式栈版 DFS。3.3 两种遍历顺序为什么都能得到正确答案BFS 是一圈一圈向外扩张先处理离起点最近的格子DFS 是一条路走到黑碰到死胡同再回头。虽然访问顺序完全不同但最终覆盖的格子集合完全一样因为决定“是否属于同一细胞”的因素只有连通性和遍历顺序没有关系。我个人建议至少把两种写法都 AC 一遍。原因很简单BFS 是很多最短路径题的基础DFS 则更容易让你理解递归和回溯。P1451 这种数据范围小、逻辑单纯的题目是练习两种遍历方式的最佳试验田。今天的你在这道题上把队列和递归都吃透明天遇到“迷宫最短步数”“单词接龙”这类题就不会手忙脚乱。4. 实战中容易踩的坑读入格式、方向选择与递归深度4.1 最大的坑输入行没有空格不能直接当整数读我见过相当一部分同学在这道题上栽跟头不是因为 BFS 写错而是因为读入方式不对。题目给出的矩阵每一行都是一个连续的字符串比如一行可能是0234500067这一整行数字之间没有空格。如果天真地写一个双重 for 循环然后每次 cin 一个整数会发生什么以“0234500067”这一行为例cin x 读到的是一个十进制整数 234500067而不是 9 个独立数字字符。前导 0 会直接消失数据损坏结果必然错误。正确的读法是把每一行按字符串读入。比如scanf(%s, grid[i]);这样 grid[i][j] 就是第 i 行第 j 列的字符判断时用字符 0 而非数字 0。这也是我上面的代码里统一写 grid[nx][ny] 0 的原因。一定要记住在这类网格题里看到“每行一个字符串”的输入格式就老老实实读字符串。4.2 四方向还是八方向题目没说清楚就吃大亏P1451 明确说的是“上下左右相邻”也就是四连通。但很多类似题目默认是八连通即斜对角也算相邻。这两种规则统计出的结果可能完全不一样。举一个极端的例子1 0 0 1按四连通规则两个 1 之间没有上下左右方向的直接连接所以答案是 2。按八连通规则它们斜对角相邻属于同一个区域答案是 1。就这么一个规则差异答案直接翻倍。所以做题时一定要把题干的“相邻”二字看清楚。P1451 是四连通不要自作聪明扩展成八连通。如果你想验证自己没理解错可以自己构造一个小矩阵手算一遍再提交代码对比输出。很多 OJ 题目里样例就是用来验证规则理解的不要跳过样例只闷头写。4.3 递归深度的隐患小数据没事大数据要提前防前文提过递归爆栈的问题这里再展开说。P1451 的数据范围是 100×100最坏情况下非 0 格子全部连成一条蛇形地带DFS 递归深度也能到 10000 层左右。主流 OJ 的默认栈空间通常能扛住这个量级所以这道题直接用递归没问题。但如果你把这道题的代码原封不动拿到一个 2000×2000 的类似题目里递归深度就可能冲到 400 万层那基本必爆。比赛时遇到这种情况我会毫不犹豫改用 BFS。初学阶段不需要过度担心性能但心里要有这根弦递归虽然好写但不是无限制的。如果你确实想用 DFS 又担心递归栈可以改成显式栈。核心思路和 BFS 一模一样只是把 queue 换成 stack把 front()/pop() 换成 top()/pop()stackpairint, int st; st.push(make_pair(sx, sy)); grid[sx][sy] 0; while (!st.empty()) { int x st.top().first; int y st.top().second; st.pop(); for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 || nx m || ny 0 || ny n) continue; if (grid[nx][ny] 0) continue; grid[nx][ny] 0; st.push(make_pair(nx, ny)); } }显式栈版 DFS 既保留了“深度优先”的访问顺序又不会占用系统调用栈是折中的方案。当然对 P1451 而言直接递归就完全够用了。4.4 数组大小和读入的细节开大一点省掉一堆烦恼矩阵最大 100×100很多同学习惯开 char grid[100][100]。这其实有一个隐患如果某一行恰好读满 100 个字符字符串末尾的 \0 会写到下标 100 的位置数组越界。在 OJ 上这类越界不一定立刻报错但它可能导致内存里的其他数据被意外篡改出现很难排查的“玄学错误”。我的习惯是统一开成 char grid[105][105]或者 110留出足够的余量。另一个更安全的做法是使用 vector int m, n; cin m n; vectorstring grid(m); for (int i 0; i m; i) { cin grid[i]; }vector 的方式不需要关心第二维边界代码也更接近现代 C 风格。不过 OJ 上 scanf 配合固定数组的写法依然非常主流二者没有高下之分看你的习惯。我自己的建议是正式比赛用数组 scanf 图快日常练习可以用 vector 图省心。5. 跳出 OJ这道题背后真正的应用场景5.1 图像处理里的连通区域标记如果你以为连通块计数只是算法竞赛的自嗨那就低估它了。在图像处理领域有一项非常基础的操作叫“连通区域标记”就是把二值图像中像素值为前景色的区域逐个分离出来。二值图像通常就是 0 和 1 的矩阵和这道题的模型几乎一模一样。举几个现实例子。车牌识别系统在分割字符时会先把图片二值化然后找出每一块连通的白色像素区域每一块对应一个字符医学影像分析中医生想快速知道某张 CT 图里有几个疑似病灶区域自动统计连通块数量就是第一步工业质检里检测电路板上的焊点数量同样会用到连通区域分析。这些系统底层的算法正是 flood fill也就是这道题的 BFS/DFS 写法。5.2 从“计数”到“最大面积”一道题能变出多少花样P1451 只是连通块计数的原始版本。把问题稍微改一改就能延伸出一串题目求最大连通块的面积在 BFS 或 DFS 的过程中记录当前块包含的格子总数维护一个最大值。求每个连通块的边界长度当发现相邻格子越界或者为 0 时就说明当前格子是边界的一部分可以计数。求连通块内部是否有空洞需要结合更复杂的遍历规则。如果地图很大且需要动态更新可以考虑用并查集合并连通区域而不是每次重新遍历整张图。这些题的核心都是同一套扫描加扩散只是在外层多包了一层业务逻辑。这就是为什么我很强调把基础模板练熟模板熟练后所有变体都只是在这个骨架上做增量修改。5.3 刷题建议拿到网格题先固定三步我给身边准备算法竞赛的朋友讲这道题时总会让他们记住一个套路看到二维网格题不管题目包装多花哨先问自己三个问题。第一连通规则是什么四方向还是八方向哪些格子算障碍物。本题中障碍物是 0可以走的是非 0 数字。第二访问标记怎么做用 vis 数组还是原地修改。这决定了代码的简洁程度。第三外层扫描和扩散函数怎么分工把主循环和 BFS/DFS 分开写后面排错会轻松很多。这三步只要想清楚剩下的就是机械地填代码。P1451 是这样“扫雷”里的空白区域展开是这样游戏里“魔法棒”选区填充也是这样。你以后做题会发现很多“看起来很难”的题底层理念早就见过。最后再分享一个小技巧。我最初写这道题的时候偷懒只写了 DFS因为代码短通过之后就以为万事大吉。等到做迷宫最短路径题时才发现队列版 BFS 写得不够熟现场磕磕绊绊浪费了不少时间。所以不要满足于一种写法至少把 BFS 和 DFS 都 AC 一遍再用原地标记版本跑一遍三种实现都吃透。以后见到任何网格遍历题你都能顺手选出最合适的工具。