每次机考刷题到“图论/搜索”这一块，LeetCode 200“岛屿数量”基本是绕不开的题目。很多人看到“岛屿数量”觉得简单，DFS一套就完事，实际上机考环境下翻车的比例相当高。我见过不少候选人代码思路是对的，但一跑测试就出问题：重复计数、死循环、数组越界、甚至输入读取都出错。这篇文章把这道题彻底拆开，从三种解法到机考细节，再到变体题和面试追问，尽量一次讲透。不管你是刷题计划排在第10天还是第100天遇到它，这篇都能帮你少走几个弯路。
1. 看懂题目之前，先把两个容易错的理解纠正过来
1.1 二维网格里的“连接”到底怎么定义
题目给的输入是一个m x n的二维字符数组，里面只有'1'（陆地）和'0'（水）。要统计的是“岛屿数量”，所谓岛屿，就是上下左右四个方向连在一起的'1'组成的连通块。
需要特别注意，斜对角方向不算连接。比如下面这个 2x2 网格：
1 0 0 1这里有两个岛屿，而不是一个。很多人在白板上画图时会习惯性把对角也连起来，这就是第一处容易出错的地方。面试或者机考时，如果题目里没有明确说明“四连通”，一定要开口确认一句，或者自己在代码注释里写清楚“上下左右四个方向”。
1.2 题目的核心考点不是“搜索”，而是“标记”
这道题的搜索本身很简单——遍历每一个格子，遇到一个没访问过的'1'，就把整块连通区域全部找出来，计数器加一。真正的难点在于：怎么保证同一个岛屿不会被重复计数。
解决思路有两个方向：一是额外开一个visited二维数组，走过就标记；二是直接在原数组上把访问过的陆地改成'0'，这种“走一个沉一个”的做法有个形象的说法叫“沉没法”。我推荐机考时用沉没法，因为它省掉了visited数组的初始化、判断和内存开销，代码也更短。所以这道题的本质可以概括成一句话：遍历 + 标记，二者缺一不可。只遍历不标记，同一个'1'会被重复遍历无数次，直接死循环。
2. DFS解法：机考时的首选写法，以及四个一次过的细节
2.1 思路讲给面试官听的一分钟版本
DFS（深度优先搜索）是最直观的解法。给面试官讲思路时，我会用这个版本：
我遍历整个网格，每当遇到一个没有被访问过的
'1'，我就认为发现了一个新岛屿，然后把岛屿数量加一。接下来从这个格子的四个方向递归搜索，把所有相邻的'1'全部标记成已访问，避免后续重复计数。
这段表述里有三个关键词：遍历所有格子、遇到'1'就计数、递归标记连通区域。把这三句话说清楚，面试官就知道你理解到位了。
复杂度方面，每个格子最多被访问一次，所以时间复杂度是O(m * n)。空间复杂度是递归栈的深度，最坏情况下整个网格都是陆地，递归深度会达到m * n，所以最坏是O(m * n)。
2.2 Java版本的DFS实现
我直接给出一个可以一次通过的版本：
class Solution { public int numIslands(char[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } int m = grid.length; int n = grid[0].length; int count = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == '1') { count++; dfs(grid, i, j); } } } return count; } private void dfs(char[][] grid, int i, int j) { if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || 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); } }很多人的写法和我这个很像，但细节上有几个差异。注意我的边界判断是放在递归函数开头，而且先判断越界，再访问数组元素。如果把grid[i][j] == '0'写在前面，i 已经越界时就会抛出数组下标异常。这个顺序问题在笔试里特别常见。
2.3 四个细节，决定你能不能一次过
第一个细节：字符别写错。判断的是'1'和'0'，这是字符 char 类型，不是数字 1 和 0。写grid[i][j] == 1不会报编译错误，但永远匹配不上，最终结果会是 0。这个坑看似低级，但机考紧张时真的有人会犯。
第二个细节：沉没操作的时机。grid[i][j] = '0'要在进入递归之前就执行，也就是在 dfs 函数体的开头。如果你先递归四个方向，最后再置为'0'，递归过程中相邻格子还会反向访问回当前格子，造成重复遍历，极端情况下会栈溢出。正确的做法是“先沉没，再扩散”。
第三个细节：空输入判断。有的测试用例会给你grid = []，如果没做判空，grid[0]这行代码会直接抛异常。我习惯写grid == null || grid.length == 0 || grid[0].length == 0，三道保险全部加上，宁可多判断也不要少判断。
第四个细节：递归深度问题。如果你用的是 Java、C++，递归默认栈空间通常够用。但如果用 Python，默认递归深度只有 1000 层左右，遇到 1000x1000 全'1'的极端用例，DFS 很容易 RecursionError。这种情况就要考虑下一节的 BFS 解法了。
3. BFS解法：不依赖递归，矩阵很大时的稳妥退路
3.1 什么时候应该换BFS
面试官追问“如果网格特别大，DFS 会不会爆栈”时，你如果能立刻给出 BFS 方案，会是明显的加分项。BFS（广度优先搜索）用队列代替调用栈，没有递归深度限制。当矩阵达到几百乘几百甚至更大，且陆地连通区域很大时，BFS 更安全。
另外有些机考的平台对递归不友好，比如某些 Python 环境、某些嵌入式方向的在线笔试，递归嵌套过深会直接被判运行时错误。所以 BFS 不是一个备胎，而是一个必须掌握的保底方案。
BFS 的核心流程：遇到一个新的'1'时，把它入队然后立马标记为'0'。队列不是空时就弹出队首元素，检查它的四个邻居，只要是'1'就入队并标记。每完成一次这样的过程，就说明发现了一个完整岛屿。
3.2 Java版本的BFS实现
class Solution { public int numIslands(char[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } int m = grid.length; int n = grid[0].length; int count = 0; int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == '1') { count++; grid[i][j] = '0'; Queue<Integer> queue = new LinkedList<>(); queue.offer(i * n + j); while (!queue.isEmpty()) { int code = queue.poll(); int x = code / n; int y = code % n; for (int[] dir : directions) { int nx = x + dir[0]; int ny = y + dir[1]; if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '1') { grid[nx][ny] = '0'; queue.offer(nx * n + ny); } } } } } } return count; } }这里我用了一个小技巧：队列里不存int[]{x, y}，而是用一个整数i * n + j把二维坐标编码成一维。好处是两个：一是Queue<Integer>比Queue<int[]>省内存和对象创建开销；二是入队时不需要额外创建数组对象，机考环境下性能更稳。解码也很简单，x = code / n，y = code % n。
3.3 BFS操作里最容易踩的坑：入队时必须立刻标记
这个坑我必须单独拿出来说，因为它非常隐蔽。很多人的 BFS 写法是“出队时再标记已访问”，也就是下面这样：
int code = queue.poll(); int x = code / n; int y = code % n; grid[x][y] = '0'; // 错误示范：出队时才标记这样写的问题在于，同一个格子可能被它的多个邻居重复入队。举个简单的例子，格子 A 和格子 B 都紧挨着格子 C，A 先入队了 C，B 入队时发现 C 还是'1'，也把 C 入队。结果队列里就出现两个 C，虽然最终结果可能碰巧还是对的，但会造成大量重复计算，极端情况下队列膨胀得很厉害。
正确的做法是模拟“扩散”的过程：一个格子一旦被入队，它就已经是被发现和认领的状态，必须立即在入队那一刻把grid改成'0'。这有点像你报名参加活动，一旦登记成功，名单上立刻划掉你的名字，而不是等活动当天再划。
4. 并查集解法：把网格变成集合合并问题
4.1 为什么还要学第三种解法
面试时如果面试官问“除了 DFS 和 BFS，这道题还能怎么做”，你如果能说出并查集（Union-Find），印象分又会不一样。这道题本质上是在统计“连通分量”的个数，而并查集恰好就是专门解决连通性问题的数据结构。
并查集的思路是：一开始把每个是陆地的格子都看成独立的集合，然后检查相邻格子，如果两个相邻格子都是陆地，就把它们合并到同一个集合里。每合并一次，集合总数减一。最后剩下的集合数量就是岛屿数量。
4.2 二维坐标的一维编码
并查集里需要给每个格子一个唯一的 ID。最常用的做法还是id = i * n + j。这样整个m * n的网格就被映射成了一个长度m * n的一维数组。
我在并查集的初始化阶段，只对'1'的格子做初始化，每个陆地的parent指向自己，count加一。水格子的parent保持默认值，不参与统计。
4.3 Java版本的并查集实现
class Solution { private class UnionFind { int[] parent; int[] rank; int count; public UnionFind(char[][] grid, int m, int n) { parent = new int[m * n]; rank = new int[m * n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == '1') { int id = i * n + j; parent[id] = id; count++; } } } } public int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); // 路径压缩 } return parent[x]; } public void union(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) { return; } // 按秩合并，尽量让树更矮 if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; } count--; } } public int numIslands(char[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } int m = grid.length; int n = grid[0].length; UnionFind uf = new UnionFind(grid, m, n); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == '1') { int id = i * n + j; // 只需要检查右边和下边，避免重复合并 if (i + 1 < m && grid[i + 1][j] == '1') { uf.union(id, (i + 1) * n + j); } if (j + 1 < n && grid[i][j + 1] == '1') { uf.union(id, i * n + j + 1); } } } } return uf.count; } }这里有两个细节值得说。一是只需要检查右边和下边。因为遍历顺序是从左上到右下，当前格子的左边和上边其实已经在之前的格子里检查过了。如果四个方向都检查，合并操作会重复执行，虽然 union 里有rootX == rootY的早退逻辑，不会出错，但白白浪费时间。二是路径压缩和按秩合并都做了，这是在面试中展示你对算法有体系化理解的加分点。
复杂度方面，并查集操作近似常数级，整体时间复杂度约O(m * n * α(m * n))，其中α是反阿克曼函数，可以近似理解为常数。空间复杂度O(m * n)。
4.4 面试里什么时候掏出并查集
我的建议是：机考笔试时优先写 DFS 或 BFS，因为代码短，不易出错。面试聊天环节如果面试官主动问“还有更好的办法吗”，或者追问“如果这个地图是动态变化的，陆地会不断新增，你怎么办”，这时候再引入并查集。
动态场景是并查集的真正用武之地。比如你维护一个实时地图，每次新增一块陆地就更新岛屿数量，DFS 和 BFS 每次都要重新全图扫描，而并查集可以在新增陆地时只做局部合并，非常高效。这也是为什么很多进阶题，比如“岛屿数量 II”、“连通网络的操作次数”，本质都在考并查集。
5. 机考输入的差异与现场排查清单
5.1 LeetCode风格和ACM风格的差异
LeetCode 风格的题目已经帮你封装好了方法签名，你只需要写public int numIslands(char[][] grid)。但不少公司的机考平台是 ACM 风格，需要自己从标准输入读取数据。这个差异是很多只刷 LeetCode 的人翻车的重灾区。
ACM 风格的 Java 模板可以参考：
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); sc.nextLine(); // 吃掉第一行末尾的换行符 char[][] grid = new char[m][n]; for (int i = 0; i < m; i++) { String line = sc.nextLine(); grid[i] = line.toCharArray(); } System.out.println(new Solution().numIslands(grid)); } }这里有个细节：nextInt()读完 m 和 n 之后，输入流里还留着一个换行符，如果不加sc.nextLine()吃掉它，接下来nextLine()读到的会是空字符串。这个坑我见过太多次了，几乎每场 ACM 风格笔试都有人栽在这里。
Python 风格类似：
import sys def main(): data = sys.stdin.read().strip().split() if not data: return m, n = int(data[0]), int(data[1]) grid = [] idx = 2 for _ in range(m): grid.append(list(data[idx])) idx += 1 print(numIslands(grid))推荐用sys.stdin.read()一次性读入再 split，比一行一行input()要快，面对大输入时也更稳。
5.2 我自己遇到过的五个现场问题
第一个是把'1'写成了1。这个连编译都不报错，结果返回 0，很难排查。
第二个是空数组判断不够。只判断了grid == null，忘了处理grid.length == 0，结果遇到空网格直接数组越界。
第三个是修改了原始数组，但面试官不允许。有的面试官会强调“不要改动输入数据”，这时候就不能用沉没法，得额外开一个visited数组。我的建议是写代码前先问一句：“我可以直接修改传入的 grid 吗？”这个提问本身也是加分项，说明你有工程意识。
第四个是方向数组写错。BFS 里四个方向写成{{-1,0},{1,0},{0,-1},{0,1}}，少写一个或者正负号写反，都会导致漏掉一部分岛屿。
第五个是递归边界顺序写反。先访问数组再判断越界，导致越界异常。记住：先判边界，再取元素。
5.3 一个简单的现场验证方法
机考写完代码后，别急着提交。我会在草稿纸上或者心里快速跑三个用例：
- 最小用例：
[["1"]]，期望结果是 1。 - 空网格：
[]，期望结果是 0。 - 一个稍微复杂点的用例：
1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1这个图有三个岛屿：左上角的 2x2 方块算一个，第三行第三列单独一个，右下角两个连在一起一个。如果代码输出 3，基本就对了。手算用例比直接提交再等结果要快得多，也能帮你提前发现逻辑错误。另外一个必查点：测试完是否不小心把grid[i][j] == '1'写成了赋值=。这种低级错误很尴尬，却真实发生过多次。
6. 变体题与面试追问：把一道题变成一类题
6.1 三个最常见的变体题
面试官不会总满足于考原题。“岛屿数量”最常见的三个变体是：
- 最大岛屿面积：DFS/BFS 过程中统计连通区域包含多少个
'1'，取最大值。 - 岛屿周长：遍历每个陆地格子，如果它的某个方向是水或者越界，周长就加一。
- 闭合岛屿数量：边界上的岛屿不算岛屿，只统计完全被水包围的岛屿。解决思路是先从四条边界 DFS 把所有和边界相连的陆地淹没，再按原题方法统计。
这三个变体的代码改动都不大，核心还是“遍历 + 标记”框架。我面试时会主动提一句：“这道题考的是连通分量计数，常见的变体有求最大面积和求周长，基本思路一样。”这句话往往能引导面试官顺着你熟悉的方向提问。
6.2 面试追问的几点应对思路
如果面试官继续加压，可能会问：
- “如果矩阵特别大，内存放不下怎么办？”答案是分块处理，同时只保留相邻块的边界信息，类似外部排序的思维。
- “如果网格里的陆地是动态增加的，怎么办？”答案就是前面提到的并查集。
- “如果需求是计算岛屿数量，还要标出每个岛屿里的所有坐标点呢？”这就是在做连通区域标记，在图像处理里叫“连通域标记”，可以扩展到图像分割场景。
我个人体会是，这道题的价值不在于背答案，而在于它串起来的几个核心能力：二维数组的遍历、递归与非递归的选择、连通性建模、还有从静态问题扩展到动态问题的迁移能力。把这些想明白了，这道题就不再是一道孤立的题目，而是一整个搜索类问题的地基。
最后分享一个我自己的小习惯。刷完这道题之后，我会强迫自己不看任何参考，分别把 DFS、BFS、并查集三种写法各写一遍，写到无脑完成的程度。因为机考现场根本没有时间让你现场推演逻辑，能做到不用过脑子就写出框架，遇到这道题才是真的稳。希望这篇把细节拆透的文章，能让你在这个题上一次过、不返工。
