1. 题目分析与思路演进1.1 这题到底在考什么LeetCode 第 200 题“岛屿数量”是图论入门绕不开的一道经典题也是各大厂笔试、面试的高频题。题目本身很直白给一个二维网格1表示陆地0表示水四连通上下左右相邻的陆地算同一个岛屿问总共有多少个岛屿。我在带新人刷题和帮朋友复盘笔试题时发现很多人第一眼看到这题的反应是“这不就是数连通块吗”但真上手写 C 语言实现反而会出现一堆莫名其妙的问题。原因在于这道题虽然算法思想不难但用 C 语言实现时输入处理、边界检查、递归深度、指针操作这些环节任何一个细节没处理好都会直接导致运行错误或者答案不对。这道题的核心考点有三个层面算法层面是否能识别出这是一个经典的连通分量计数问题并想到用 DFS、BFS 或并查集解决。编程层面C 语言中二维数组的传参方式、数组越界的防御性检查、递归/队列的代码组织能力。细节层面边界条件比如空网格、只有一行、只有一列是否能正确处理。1.2 为什么推荐从 DFS 入手解这题有三条常规路线DFS深度优先搜索、BFS广度优先搜索、并查集Union-Find。三者的时间复杂度和空间复杂度各有取舍后面我会详细对比。这里先说为什么初学者优先掌握 DFS 版本。DFS 版本的思路可以浓缩成一句话遍历每个格子遇到1就把它所在的整块陆地全部“淹没”掉。所谓淹没就是把连在一起的1全部改成0或其他标记避免后面重复计数。选择 DFS 作为入门第一版理由很实际代码量最少核心递归函数不到二十行。思路与直觉一致顺着“往四个方向一直走”的思维方式就好。不需要额外写数据结构——BFS 在 C 语言中要手写队列并查集要维护 parent 数组并处理路径压缩代码量明显更多。提示先彻底吃透 DFS 版本再去看 BFS 和并查集可以避免把不同思路的细节搅在一起学习曲线更平滑。1.3 复杂度的直观理解时间复杂度 O(M×N)M 是行数N 是列数。为什么能做到这个复杂度因为每个格子最多被“进入”一次——被遇到时如果它是1递归调用会把一整块岛屿清零如果它是0或已经被清零既不会计数也不会进入递归。平均每个格子被检查的次数是常数级的。空间复杂度最坏也是 O(M×N)这发生在整个网格全是陆地的情况。这时候递归深度会达到网格的格子总数比如一个大面积的1连通块递归调用栈会一路压下去。这是初学者容易忽略的点因为 LeetCode 的题目通常不刻意卡栈大小但在某些 OJ在线评测系统上如果网格特别大且栈空间受限DFS 可能栈溢出。遇到这种情况优先改用 BFS。2. 输入输出与函数签名细节2.1 不是所有“岛屿数量”题目输入都相同先说一个容易踩的坑同样是“岛屿数量”不同平台题目的输入定义可能不一样。LeetCode 200 题的函数签名是int numIslands(char** grid, int gridSize, int* gridColSize);其中grid是二维字符数组gridColSize是一个一维数组记录每一行的列数不过做题时一般默认每行列数相同直接用gridColSize[0]即可。这里的char类型元素存储的是字符1和0而不是整数 1 和 0。但很多学校机房练习系统、或者 ACM 风格的题目输入可能是先给行列数再读入整数矩阵比如3 3 1 1 0 0 1 0 0 0 1这种输入下数据的类型是整数int比较时要用grid[i][j] 1而不是grid[i][j] 1。这个差异看起来微小但真的能让调试从五分钟拉长到两小时。拿到题目先看清输入定义再动手。2.2 LeetCode 风格入参怎么处理如果是在 LeetCode 上做题函数签名已经给定不需要自己写读入逻辑直接实现算法就好。在本地调试的时候如果需要自己做输入解析可以参考下面的写法#include stdio.h #include stdlib.h char** readGrid(int* m, int* n) { scanf(%d %d, m, n); char** grid (char**)malloc((*m) * sizeof(char*)); for (int i 0; i *m; i) { grid[i] (char*)malloc((*n 1) * sizeof(char)); scanf(%s, grid[i]); } return grid; }这里有个细节用scanf(%s, grid[i])读取字符串时它会自动在末尾补\0所以一维数组长度要开n 1。读完一行后缓冲区里残留的换行符不用特意处理因为%s会自动跳过空白字符。这块是刚写 C 的读者容易困惑的地方。2.3 二维数组传参的 C 语言基础C 语言中二维数组传参是很多人的痛点。LeetCode 的char** grid实际上是一个“指针数组”的结构grid是指向若干char*的指针每个char*指向一行的起始位置。这种结构在内存中不一定是连续的大块但你完全可以把它当二维数组用下标访问方式是grid[i][j]。如果自己写函数封装 DFS需要注意在递归函数里你需要同时知道 grid、行数 gridSize、列数 gridColSize[0] 或行列的最大边界。列数不等于每个字符串的长度因为字符数组末尾有一个看不见的\0。所以常见做法是把列数显式传进 DFS 函数或者用一个全局变量保存。为了代码可读性我习惯把行数和列数作为 DFS 函数的参数传递。另外提醒一个新手高频问题如果自己用int二维数组做这道题要么固定分配一个大数组比如int grid[500][500]要么用动态分配。动态分配时要注意内存释放LeetCode 上函数返回后测试框架会统一处理但本地练习时不要忘记free否则用 Valgrind 检查会报内存泄漏。3. DFS 核心实现与关键技巧3.1 基础版 DFS 逐行拆解先给出 DFS 最直接、可读性最好的版本void dfs(char** grid, int gridSize, int colSize, int i, int j) { // 边界检查 非陆地检查 if (i 0 || i gridSize || j 0 || j colSize || grid[i][j] ! 1) { return; } // 标记已经访问过直接把陆地改成水 grid[i][j] 0; // 向四个方向递归 dfs(grid, gridSize, colSize, i - 1, j); // 上 dfs(grid, gridSize, colSize, i 1, j); // 下 dfs(grid, gridSize, colSize, i, j - 1); // 左 dfs(grid, gridSize, colSize, i, j 1); // 右 } int numIslands(char** grid, int gridSize, int* gridColSize) { if (gridSize 0 || grid NULL) { return 0; } int colSize gridColSize[0]; int count 0; for (int i 0; i gridSize; i) { for (int j 0; j colSize; j) { if (grid[i][j] 1) { count; dfs(grid, gridSize, colSize, i, j); } } } return count; }核心逻辑只有三块遍历双重循环扫描所有格子。触发遇到1说明发现了一个新岛屿计数加一。淹没从当前格子出发递归把整块陆地清零。很多教材把这种做法叫“沉岛法”名字很形象。最关键的设计就是在递归前立刻把grid[i][j]置为0。这个标记动作是必须的如果不做递归会无限循环——因为它会反复访问同一个格子。3.2 原地标记省空间的设计逻辑可能有读者会问为什么不另外开一个visited二维数组来记录访问状态这样做在工程上更规范但在这道题里没有必要。原因在于题目明确给了二维网格的修改权限且我们并不需要保留原始的陆地信息。把1改成0和开一个额外的visited数组本质上都是“标记已访问”但前者省掉了一整块 O(M×N) 的额外空间还能直接省去“每个格子都要初始化 visited”的遍历时间。这个“能改就改能省就省”的思路在竞赛和面试中很实用。不过要记住一个前提如果题目不让你修改原数组你就必须用 visited 方案。比如有的变体题考察“你不可以修改 grid”这时候就要在 DFS 里维护一个bool visited[M][N]或者用int数组标记每一个访问过的坐标避免重复。3.3 五个让我少走很多弯路的细节第一边界检查放在递归函数的第一行比“调用前判断”更稳妥。有人喜欢在dfs调用前写四个if判断边界这样也能工作但代码冗余而且容易漏掉一个方向。放在函数入口统一判断是最清晰、最不容易出错的做法。第二用方向数组代替四个递归调用可读性因团队而异但我个人强烈推荐在代码量大的时候用。当你有四五个方向需要遍历时比如八连通手写八个递归调用是灾难int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int k 0; k 4; k) { int ni i dirs[k][0]; int nj j dirs[k][1]; dfs(grid, gridSize, colSize, ni, nj); }第三如果grid可能为空先判断gridSize 0再取gridColSize[0]。LeetCode 的测试用例包含grid []的情况如果你的代码先解引用gridColSize[0]就会崩溃。第四注意grid[i][j] ! 1的判断。有人在递归里写成grid[i][j] 0这会出现问题如果格子已经被标记成0它确实会 return但如果格子本来是1且刚被改成0判断就没有问题。真正要避开的是把判断写成grid[i][j] 0——这在字符数组里是永远不为真的因为字符0的 ASCII 值是 48不是数值 0。第五递归深度和栈溢出的关系。DFS 在极端情况下的递归深度等于岛屿格子数写成int类型可能会导致一个超大面积的岛屿把栈耗尽。LeetCode 200 题的数据范围一般不会触发这个限制但在一些平台的变体题中我遇到过 500×500 的极限数据C 语言默认栈还能勉强扛住但如果到了 2000×2000 级别DFS 很可能直接爆栈。这个时候应当考虑 BFS。3.4 一个容易被忽略的返回值陷阱C 语言中count在numIslands中返回的是int。很多人觉得没问题但在某些平台上gridSize和colSize可能达到很大规模比如 1000×1000最大岛屿数量理论上有 50 万虽然离int上限远得很但如果题目数据将来升级到 10000×10000 还是能存下。这里真正想提醒的是不要因为想省变量就写成return count;时少写了累加逻辑。我见过有同学把count写在dfs里导致每递归一次计数一次最后返回一个巨大的错误数字。正确的语义是只有“发现一整块新岛屿”时才计数而不是“访问每个格子时都计数”。4. BFS 手动队列实现解析4.1 C 语言写 BFS 要先解决队列BFS 的思路同样非常简单从陆地格子出发把它所有相邻的陆地一层一层往外扩展。扩展顺序不重要关键是不重不漏。C 语言不像 C 或 Java 那样有现成的std::queue必须自己实现一个队列。这一步对很多刷题的人来说反而是 BFS 版本的主要门槛。用一个数组模拟队列是最常见、最不容易出错的做法。队列数组的元素是坐标可以用结构体存(i, j)也可以直接把坐标编码成单个整数用i * colSize j编码取出时用除法还原。编码的方式省一个结构体定义代码短一些但可读性稍差int queue[MAX_SIZE]; int head 0, tail 0; queue[tail] i * colSize j; // 入队解码时int pos queue[head]; int curI pos / colSize; int curJ pos % colSize;MAX_SIZE 的开法有两种思路直接开gridSize * colSize 5确保足够大或者动态分配。由于栈上开大数组在部分 OJ 上有风险我通常用动态分配但如果你确定网格规模在几千乘几千以内静态数组int queue[1000000]也行。4.2 完整 BFS 参考实现void bfs(char** grid, int gridSize, int colSize, int startI, int startJ) { int total gridSize * colSize; int* queue (int*)malloc(total * sizeof(int)); int head 0, tail 0; int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; grid[startI][startJ] 0; queue[tail] startI * colSize startJ; while (head tail) { int pos queue[head]; int x pos / colSize; int y pos % colSize; for (int k 0; k 4; k) { int nx x dirs[k][0]; int ny y dirs[k][1]; if (nx 0 nx gridSize ny 0 ny colSize grid[nx][ny] 1) { grid[nx][ny] 0; queue[tail] nx * colSize ny; } } } free(queue); } int numIslands(char** grid, int gridSize, int* gridColSize) { if (gridSize 0 || grid NULL) { return 0; } int colSize gridColSize[0]; int count 0; for (int i 0; i gridSize; i) { for (int j 0; j colSize; j) { if (grid[i][j] 1) { count; bfs(grid, gridSize, colSize, i, j); } } } return count; }这段代码里有一个特别关键的操作元素入队的同时立刻把grid[nx][ny]置为0。这就是 BFS 的重灾区。如果不立刻标记同一个格子可能在后续的扩展中被多个邻居重复入队造成大量无效计算甚至队列溢出。我在带新手时经常让他们专门盯这一点因为 “虽然 BFS 逻辑简单但这个错误几乎人人犯”。4.3 BFS vs DFS 的实际差异两个算法在本题上的核心区别是空间增长模式。DFS 的空间消耗跟递归深度绑定也就是跟连通块大小相关BFS 的空间消耗跟队列最宽时的宽度相关也就是跟某一层扩展出的节点数相关。两者最坏都是 O(MN)但在实际数据上差别不小。如果网格是一个很窄很长的形状比如 1×100000DFS 深度会达到 100000 甚至可能爆栈而 BFS 队列里最多同时存几个点内存占用极小。反过来如果网格接近正方形且陆地大而密集BFS 队列可能瞬间膨胀到很大规模而 DFS 递归深度则相对可控。所以具体选哪种要看平台限制和题目数据范围。从面试角度来说建议至少掌握 DFS 和 BFS 两种写法。因为面试官常会追问“如果网格特别大怎么办”“如果栈空间不够怎么办”这些问题对应的就是算法选型和复杂度分析。4.4 静态队列的容量计算技巧前面代码里用total gridSize * colSize来分配队列空间。这里有个数学上的保证任何一个格子最多入队一次所以队列长度永远不会超过总的格子数。因此按total分配一定是够用的。这个结论在任何 BFS 题型里都成立只要你能保证“入队即标记”这个不变式。如果选择静态数组一种常见做法是写int queue[1000005]这在竞赛中确实可行但不够优雅而且在某些严格要求栈空间的嵌入式场景中可能出问题。换成动态分配一行代码就能解决问题代价是记得free。用动态分配还有一个额外的好处如果题目有多个测试用例每次调用bfs独立分配、独立释放不会因为上次运行残留数据而出错。5. 并查集思路与多方案对比5.1 并查集如何解决本题并查集Union-Find的思路不同于 DFS/BFS 的直接遍历它的核心是合并。所有陆地格子初始时各自为营每个格子的父节点指向自己。遍历时只要发现某个格子右边或下边只需检查两个方向即可也是陆地就把这两个格子所在的集合合并。最终统计有多少个陆地格子的父节点指向自己就是岛屿数量。因为只需要检查右邻居和下邻居就能把所有相邻的陆地合并到同一集合不需要四个方向都检查。这一技巧能省一半的判断次数值得记住。示例代码结构大致是int find(int parent[], int x) { if (parent[x] ! x) { parent[x] find(parent, parent[x]); // 路径压缩 } return parent[x]; } void unionSet(int parent[], int x, int y) { int rx find(parent, x); int ry find(parent, y); if (rx ! ry) { parent[ry] rx; } }遍历时每个格子编号为i * colSize j判断右邻居和下邻居是不是1如果是就合并。最后再走一遍所有格子统计祖父是自己的陆地数量。5.2 三种解的对比与选型建议下面这张表是我做这道题时整理的对比直接抄作业用方案时间复杂度空间复杂度C 语言实现难度适用场景DFSO(M×N)O(M×N) 最坏递归栈低常规刷题、笔试首选BFSO(M×N)O(M×N) 队列中网格大、担心栈溢出并查集O(M×N×α)O(M×N) parent 数组中高考察并查集专题、需要动态连通性场景其中 α 是阿克曼函数的反函数实际可以当成常数。并查集单次查找接近 O(1)所以整体还是 O(M×N)。从面试角度DFS 是最安全的答案代码短、思路清晰、正确性容易解释。但如果面试官追问“递归深度可能很大怎么办”你可以顺势写出 BFS。并查集则适合在面试官故意引导“如果要多次查询岛屿数量或者网格动态变化”时拿出来展示进阶思维——但绝大多数面试场景不会真的要求写并查集版能用它讲清思路已经足够加分。5.3 并查集的两个编码细节第一路径压缩的递归写法可能爆栈。当集合链很长时递归版find的深度也可能很高。但并查集的路径压缩通常能有效控制树高实际刷题中极少因为find递归爆栈。如果实在不放心可以写迭代版findint find(int parent[], int x) { int root x; while (root ! parent[root]) { root parent[root]; } while (x ! root) { int next parent[x]; parent[x] root; x next; } return root; }第二合并时按秩合并会更好。上面示例里直接把parent[ry] rx如果两棵树高度相差很大长期下来树可能偏深。虽然路径压缩已经能缓解大部分问题但写成“按高度合并”才是标准做法if (rank[rx] rank[ry]) { parent[rx] ry; } else if (rank[rx] rank[ry]) { parent[ry] rx; } else { parent[ry] rx; rank[rx]; }这个细节在面试中如果主动写出来会有加分效果因为说明你理解并查集的性能关键点。6. 常见问题与提速技巧实录6.1 五个高频报错和解决办法报错一下标越界或非法内存访问。多半是因为 DFS 递归时没有先做边界判断就访问grid[i][j]。解决方法是把边界判断放在递归函数入口的第一行而不是依赖调用前的四个 if。报错二输出很大或非常离谱。基本是计数位置放错了。检查count是不是放在“发现新岛屿”的位置而不是递归内部。报错三答案偏小。常见原因是方向遗漏比如只递归了上和左两个方向。注意题目要求是四连通而不是八连通两个方向必然出错。报错四本地运行正常LeetCode 提交却不过。要检查是否修改了函数签名、是否把char错写成int比较。LeetCode 平台会隐藏很多边界测试用例比如空数组、单行、单列。报错五BFS 版本运行超时。超时九成是因为队列入队后没有立刻标记导致大量格子重复入队复杂度退化到远高于 O(M×N)。检查所有入队操作前是否先置0。6.2 本地调试的实用配置做题时用 VSCode 写 C 语言的话调试体验其实比很多人想象的好很多。我推荐一个组合VSCode C/C 扩展 gdb。在launch.json里配置好调试器后可以在 DFS 递归函数入口打断点观察i、j、grid[i][j]的变化看递归的走向是否和自己预期一致。这比自己加printf高效得多。如果不会配置 VSCode C 语言环境也可以用更轻量的办法在关键位置加printf(i%d, j%d, grid%c\n, i, j, grid[i][j]);观察执行顺序。注意打印完之后要把这行注释掉否则提交时会造成不必要的输出导致“输出多余结果”的判题错误。6.3 几个实测有效的提速建议如果要追求极致的运行速度可以先在numIslands开头做一次提前判断如果gridSize 0或grid NULL直接返回 0。这个判断不仅是正确性要求还能让空输入用例立即返回省掉循环。配合编译器优化本地编译时开启-O2递归函数可能被优化得更好。但提交到 LeetCode 时编译器选项是固定的你唯一能控制的就是代码本身。这时候减少函数调用开销是一个思路递归函数尽量保持简洁不要在里面做太多与任务无关的判断。还有一个小技巧既然字符只有0和1两种可能边界条件判断可以写成if (grid[i][j] 0)。因为字符\0的 ASCII 值是 0字符0的值是 48任何非陆地字符的 ASCII 值都小于或等于0。这样用代替!在某些情况下可以减少一次比较操作。但坦白说现代编译器对这类微优化已经很成熟写代码时我仍然优先推荐语义清晰的! 1微优化留给编译器去做。6.4 刷完这题之后还能做什么扩展这道题是一系列图论题的“母题”。把四连通改成八连通就是“岛屿数量 II”的变体把“数岛屿”改成“找最大岛屿面积”就是 LeetCode 695 题把“陆地/水域”的概念抽象成“敌人/朋友”又是另一种连通块问题。核心的 DFS 沉岛思路几乎是一脉相承的刷透这一题后面遇到类似题目能省很多力气。对于准备竞赛的同学可以进一步把这道题和“洪水填充”联系起来。很多搜索题里的“填充”操作本质都是写一个类似的 DFS 或 BFS 遍历区别只在标记方式和状态定义。理解了这题里的沉岛操作很多迷宫类、区域填充类题目都会豁然开朗。我在实际刷题中比较深的一个体会是C 语言写这类图论题真正的门槛往往不是算法本身而是对内存、边界、输入输出的把控。把一个算法从“伪代码能跑”到“C 代码 AC”中间隔着的恰好就是这些细节。你只要把边界检查、标记时机、队列容量这几件事想清楚这道题基本就能闭着眼写出来。最后再分享一个小技巧本地自测时不妨手动构造一个全1的大网格和一个全0的网格这两个极端用例通过这道题就稳了一半。