岛屿数量这道题我在面试考场上见过至少十次。不是作为压轴难题而是作为“看你基本功牢不牢”的必答题出现。候选人写出来的版本五花八门但真正能在五分钟内给出无bug的C BFS实现还能把floodfill的思路讲清楚的人确实不多。这篇就把“岛屿数量 floodfill算法 BFS C”这条线彻底讲透题目在考什么、为什么用BFS、代码怎么组织、有哪些隐藏的坑以及怎么把这套模板迁移到别的题目上去。适合准备算法面试的C学习者、刚接触图遍历的刷题党以及想搞懂洪水填充思想但被各种题解绕晕的读者。1. 为什么这道题是BFS和floodfill的“敲门砖”题目本身看着简单给你一个二维网格1表示陆地0表示水上下左右相邻的陆地算同一个岛屿问总共有多少个岛屿。但很多人第一次写的时候会陷入一个思维误区——试图去“追踪”每一块陆地属于哪个岛屿结果代码越写越复杂。1.1 从一组0和1抽象成图这道题真正考的是你能不能把一个二维矩阵看成一张图。矩阵里的每一个格子都可以看成图里的一个节点。相邻关系上下左右四个方向就是节点之间的边。于是“找岛屿”就变成了“找这张图里有几个连通分量”——而“连通分量”的概念才是题目背后的真正考点。连通分量的意思是一堆节点互相之间能通过边到达并且这堆节点和外面的节点没有边相连。这种从矩阵到图的抽象能力在算法题里非常常见。前面你可能会想“我需要记录哪些格子已经被访问过避免重复计数”没错这就是所有图遍历问题的核心。但实现方式有很多种最常见的就是把访问过的格子标记成0——相当于把这块陆地“淹掉”下一次遍历就不会再碰到它了。1.2 floodfill算法把“查找”变成“染色”floodfill这个词字面意思是“洪水填充”。想象一下往一个坑里灌水水会顺着坑的形状蔓延开来直到填满整个坑。把这个思想用到这道题上就是碰到一块陆地就把它当成种子让“洪水”往上下左右四个方向扩散把所有相连的陆地全部淹没。等洪水停下来这一整块连通区域就被标记完了这就是一个岛屿。这个过程的核心价值在于你不需要去数每一块陆地只需要找到种子然后把整个区域染色。每做一次成功染色就说明发现了一个新的连通分量也就是一个新的岛屿。所以主循环的逻辑就变得非常简单遍历整个网格遇到1就计数加一然后调用floodfill把这一整块全部变成0。这种“找到一个点扩散处理整个区域”的模型在算法题里非常通用。比如图像处理里的油漆桶填充、扫雷里点开一片空白区域、迷宫寻路里判断两个点是否连通本质上都是floodfill的变体。这也是我一直建议大家把这道题学透的原因——它是一堆题目的公共底座后面至少四五道LeetCode题都能用这套模板改出来。2. BFS解法的完整实现与逐段拆解直接上代码先用标准BFS模板写后面再逐行解释关键决策。#include vector #include queue using namespace std; class Solution { private: int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0}; public: int numIslands(vectorvectorchar grid) { if (grid.empty() || grid[0].empty()) { return 0; } int m grid.size(); int n grid[0].size(); int count 0; queuepairint, int q; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; grid[i][j] 0; q.push({i, j}); while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 nx m ny 0 ny n grid[nx][ny] 1) { grid[nx][ny] 0; q.push({nx, ny}); } } } } } } return count; } };整个代码量不到四十行。结构上分三块方向数组、主循环、BFS内部扩散。下面说几个容易被忽略的设计点。2.1 方向数组为什么要单独声明方向约束只有上、下、左、右四个方向。如果不用dx和dy你就得写四段几乎一模一样的逻辑向上判断一行、向下判断一行、向左判断一列、向右判断一列。代码会变得冗余且容易漏改。用方向数组之后扩散逻辑被统一到了一个循环里后续如果要扩展成八个方向加上四条对角线只需要往数组里加四个组合就行int dx[8] {0, 0, 1, -1, 1, 1, -1, -1}; int dy[8] {1, -1, 0, 0, 1, -1, 1, -1};这个模式在后面的BFS题里会反复用到建议直接养成习惯。2.2 为什么“入队前标记”不是性能优化而是正确性保证注意代码里的这个细节在把相邻节点(nx, ny)加入队列之前我就立刻把grid[nx][ny]改成了0。这一步非常关键但我见过很多新手在这里犯错——他们习惯在从队列取出节点时才标记访问也就是把grid[x][y] 0放在pop之后。这样一来同一个节点很可能被多个邻居重复加入队列。举个例子假设节点A和节点B都是陆地它们都相邻节点C。BFS先扩展A发现C是陆地把C加入队列但此时C还没被标记。紧接着扩展B又发现C是陆地又把C加入队列。队列里就出现了两个C。虽然最终结果可能还是对的第二次取出来的C已经被标记过不会再扩散但队列里会塞进大量重复元素最坏情况下会多出好几倍的无效计算。正确的做法是入队前就标记访问状态。这保证了每个节点只入队一次整个BFS的时间复杂度才能严格控制在O(M*N)。2.3 主循环里的计数逻辑与“染色”动作主循环的逻辑是扫描整个网格碰到一个1就计数加一然后调用BFS把这一整块区域全部“染色”成0。这里有个很容易理解错的点BFS里的染色动作本质上就是给格子的访问状态做标记。因为题目允许修改原数组所以直接原数组标记省去了额外维护一个visited二维数组的内存开销。如果你不想修改输入数组那就需要单独开一个vectorvectorbool visited(m, vectorbool(n, false))在入队和出队时同步维护。这个方案在下一节我会详细说因为它在某些面试场景下会被要求。3. 三种思路的取舍BFS、DFS、并查集岛屿数量这道题BFS只是解法之一。实际上还有递归DFS和并查集两种主流思路它们各有各的适用场景。我把它们放在一张表里对比解法核心思想空间复杂度主要风险BFS队列层序扩散显式遍历O(min(M, N))代码稍长队列操作多DFS递归深入一条路走到底O(M*N)最坏递归栈深度递归层级深时可能栈溢出并查集合并连通分量最后统计根节点O(M*N)代码量大需要理解路径压缩和按秩合并3.1 三种解法的定位差异BFS和DFS在思想上其实是等价的都是floodfill——“从种子点出发把所有相邻的陆地全部标记”。区别只是扩散顺序不同BFS一层一层往外推像水波扩散DFS一条路走到黑再回头像探险走迷宫时在岔路口先选一条走走不通再回来。递归DFS代码最短很容易写出惊艳的版本void dfs(vectorvectorchar grid, int i, int j) { if (i 0 || i grid.size() || j 0 || j grid[0].size() || grid[i][j] 0) { return; } grid[i][j] 0; dfs(grid, i 1, j); dfs(grid, i - 1, j); dfs(grid, i, j 1); dfs(grid, i, j - 1); }但递归的致命问题在于如果网格特别大比如2000x2000的全是陆地递归深度可能达到四百万层。C默认的函数调用栈空间大约在1MB到8MB之间Windows下通常1MBLinux下通常8MB四百万层的栈帧几乎必然导致栈溢出Stack Overflow。并查集的视角则完全不同一开始把每个陆地都当成一个独立的集合遍历相邻格子时如果发现两个格子都是陆地就把它们合并到同一个集合里。最后数一数有多少个集合就是岛屿数量。并查集的好处是可以动态维护连通性不需要全图重扫。但代码量和理解成本都更高在笔试面试中除非题目明确要求动态添加岛屿否则不太推荐用它来解这道题。3.2 BFS的空间复杂度到底会不会爆炸这道题里BFS的队列空间复杂度最坏情况是O(min(M, N))。这个结论很多文章会直接说但没解释为什么。我用自己的理解说下想象一个从左上角开始的洪水填充过程。BFS是按层扩散的同一层的节点数就是这个层宽。最极端的情况是蛇形排列的陆地路径BFS的某一层可能分布在一条从左上到右下的对角线上这条对角线上能放下的节点数最多也就是min(M, N)量级。所以队列里的元素数量不会超过这一层的规模整体就是O(min(M, N))。这个空间复杂度在二维矩阵BFS里属于比较优秀的远比开一个visited二维数组要节省内存。这也是为什么BFS方案在实际工程中更容易被接受的原因之一——它的内存消耗是线性的并且常量不大。3.3 面试追问如果面试官不让你改原数组我在实际面试中遇到过几次这样的追问“如果不能修改输入的grid数组怎么办”这其实是在考察你有没有考虑过函数副作用的问题——毕竟你写的numIslands接收的是引用调用方可能还要用这个数组做其他事情。解法也很简单开一个同样大小的visited二维数组初始化为false。BFS遍历时发现陆地且visited为false就把它设true并入队。核心判断条件从grid[nx][ny] 1变成grid[nx][ny] 1 !visited[nx][ny]。时间复杂度和空间复杂度都会变成O(M*N)但输入数据被完整保留了。这个方案我在代码注释里顺手也标一下方便大家直接改。vectorvectorbool visited(m, vectorbool(n, false)); // 入队前 if (nx 0 nx m ny 0 ny n grid[nx][ny] 1 !visited[nx][ny]) { visited[nx][ny] true; q.push({nx, ny}); }4. 实测最容易翻车的五个细节刷题网站的测试用例和本地环境是有差异的。这段代码我在LeetCode、牛客网和一些线上的OJ上都跑过也遇到过一些值得注意的坑整理出来供大家参考。4.1 边界判断的短路求值陷阱C的运算符是从左到右短路求值的。如果我把判断顺序写反比如if (grid[nx][ny] 1 nx 0 nx m ny 0 ny n)那么当nx或ny越界时grid[nx][ny]这个访问是未定义行为。这在本地运行可能没事比如你分配的内存碰巧还能读但在某些OJ上会直接返回AddressSanitizer错误或者随机结果非常难排查。正确的顺序一定是先做下标范围判断再访问数组。if (nx 0 nx m ny 0 ny n grid[nx][ny] 1)这个顺序问题看似基础但实际在笔试时因为紧张写反的人并不少。我建议把这一行当成模板固定下来每次直接就写这个顺序。4.2 char型网格与模板代码带来的类型坑题目给的是vectorvectorchar网格元素是字符1和0不是整数1和0。别笑我在代码评审里真的见过把grid[i][j] 1写成grid[i][j] 1的版本。C会把grid[i][j]这个char和整数1做比较char会被隐式转换成整数ASCII码里1对应4949等于1吗永远不等于。于是整个算法会输出0个岛屿——哪怕全图都是陆地。这个坑的隐蔽之处在于编译器不会报错程序能正常跑结果就是错的。如果你用int类型的网格刷过其他题再切回char类型时特别容易踩到。4.3 把二维坐标压缩成一维省内存还是添麻烦有些题解会把pairint, int替换成一个整数比如i * n j其中n是列数。这样队列就从queuepairint, int变成了queueint内存占用确实会小一些因为pairint,int通常占8字节而一个int占4字节。但代价是每次取出队列元素后你得做一次除法运算来还原坐标int cur q.front(); q.pop(); int x cur / n; int y cur % n;乘法、除法这些操作的耗时要考虑。在数据量极大、追求极致性能的题目里节省那一点内存可能值得但在算法题这个场景下可读性比那4字节重要得多。我个人的建议是除非遇到内存限制特别明确的题目否则直接用pairint, int代码更清晰也方便调试。4.4 编译环境差异与C版本注意事项代码里用了auto [x, y] q.front()这种结构化绑定这是C17才引入的语法。如果你在牛客网或者某些老OJ上做题默认编译标准可能还是C11这行代码会导致编译失败。遇到这种情况手动换回pair的访问方式即可int x q.front().first; int y q.front().second; q.pop();另外有些OJ的编译器支持C14但未必完整支持C17所以最稳妥的做法是在写BFS的模板代码时直接用first和second或者提前确认编译标准。这个问题我吃过亏有次在某个OJ上提交直接被“compile error”打懵了最后才发现是结构化绑定的问题从那以后我对编译环境就多留了个心眼。4.5 不要用递归DFS写超大用例前面已经提到递归DFS的时间复杂度和BFS相同代码也最简洁但在深递归场景下有栈溢出的风险。实际操作中如果grid是1000x1000且全是陆地递归深度会达到一百万层大多数在线环境都会直接崩溃。所以凡是你在生产环境或者大型OJ上可能要处理的矩阵都优先考虑BFS。题目本身考的是floodfill思想不是考你递归功底没必要在风险上赌。5. 从岛屿问题到floodfill家族一套算法走天下学算法最忌讳的是“一题一记”。岛屿数量这道题最大的价值在于它是floodfill模型的完美范例。掌握了这套BFS floodfill的模板很多题目的底层逻辑都会变得清晰。5.1 油漆桶、扫雷与迷宫floodfill的通用模型floodfill的底层模型可以概括成三步找到一个满足条件的种子点。从种子点出发用一个队列或递归栈去扩散。扩散时把访问过的点标记掉防止重复处理。这个模型至少对应以下几类常见题型LeetCode 733 图像渲染给一个像素点把颜色改成新颜色并扩散到所有相连的同色像素。这就是直接的floodfill连题目描述都用的“填充”这个词。扫雷游戏翻开一个空白格周围所有空白格和数字格都会被联动翻开。这也是floodfill扩散条件从“颜色相同”变成了“是空白格”。迷宫连通性判断判断起点和终点能不能连通同样是floodfill扩散条件从“颜色相同”变成了“不是墙”。一旦理解了这套模板这些题的核心逻辑你基本都有了剩下的只是改一改扩散条件和标记方式。5.2 变体题怎么用同一套模板改在岛屿问题这个家族里还有几个经典变体本质都是在BFS遍历时额外记录一些信息岛屿最大面积LeetCode 695不再计数而是每次BFS时统计该连通区域包含多少个1取最大值。只需要在找到种子节点后把计数逻辑从“加一”改成“内部累加后比较”就行。岛屿周长LeetCode 463一道更巧妙的题不用BFS都能做。每碰到一块陆地周长加4每碰到一个相邻陆地周长减1因为重合的边不算周长。被围绕的区域LeetCode 130从边界上的O开始做BFS把这些节点标记为“不可变”剩下的O就是要被翻转成X的节点。岛屿数量IILeetCode 305需要会员这个就属于进阶题了每次动态往网格里加一块陆地问此时岛屿数量是多少。用BFS做需要全图重扫效率低用并查集做才是正解可以动态维护连通性。你看从一道题出发能延伸出一整个题族。这也是我强烈建议把岛屿数量这道题吃透的原因——它不只是一道题而是好几道题的公共底座。我自己刷这题的经验是不要急着上线提交先在纸上画一个5x5的手写矩阵模拟BFS队列的进出过程一步步走一遍。走通了再写代码。对新手来说这一步的价值比看十篇题解都大。等你把BFS和floodfill的理解固化下来后面再碰二维矩阵相关的题效率会高很多。特别是笔试时这种题往往是“送分题”能不能稳稳拿到就看平时的基本功扎不扎实。