机考刷题系列这一期落到一道绕不开的经典题LeetCode 200「岛屿数量」。只要是参加过机考或者准备过算法面试的人几乎都撞见过这道题。它题面短、理解门槛低但背后同时牵出 DFS、BFS、并查集三条技术路线而且处处是坑字符和数字的混淆、递归深度、边界越界、标记时机……任何一个点都能让你在考场上白丢一道题的分。一句话概括题目给一个由 1 和 0 组成的二维网格1 代表陆地0 代表水上下左右相邻的陆地属于同一座岛屿统计网格里岛屿的总数。就这么简单但恰恰是这种看起来简单的题最能区分出真会写代码的人和只会背模板的人。这篇文章围绕这道题把三种主流解法全部拆开结合机考场景讲清楚每一步为什么要这么写、有哪些坑、变体题怎么练。适合读这篇文章的人有三类正在准备机考的应届生想系统补图遍历基础的开发者以及那些刷过题但只记住了答案、没搞懂原理的背题党。如果你属于最后一类建议跟着代码自己敲一遍重点看我标注原因的部分收获会完全不一样。1. 题面拆解岛屿数量究竟在考什么1.1 原题回顾与输入输出约定先回顾原题。给定一个 m 行 n 列的二维网格 grid每个格子是字符 1陆地或 0水。要求计算岛屿数量其中岛屿由水平或垂直方向上相邻的陆地连片构成并假设网格四条边之外都是水。两个输入样例能帮你快速建立直觉。第一个样例11110 11010 11000 00000输出是 1因为所有陆地连成了一整片中间的水洼并没有把岛屿切开。第二个样例11000 11000 00100 00011输出是 3左上角一块、中间孤立一块、右下角一块。这题有两个约定特别容易被忽略。第一格子是字符 1 和 0不是整数 1 和 0。新手写判断时经常图省事写grid[i][j] 1在 Python 里字符和整数永远不相等于是整个计数全是 0而且由于逻辑上看不出毛病这种 bug 极难自查。第二相邻只算上下左右四个方向斜对角不算。这个规则把问题定位成四连通比图像分割里的八连通简单一档但如果刚做完棋盘、图像类的题很容易惯性把对角线也算进去导致本应分开的岛屿被合并成一座答案偏小。1.2 从数岛屿到数连通分量如果不做抽象你看到的就是一个装满 0 和 1 的表格数起来全凭感觉。但把它转成图论视角后思路会豁然开朗把每个 1 格子看成图里的一个节点把相邻陆地之间的邻接关系看成边那么一座岛屿就是一个连通分量题目要求的岛屿数量就等于整个网格图中连通分量的个数。这个抽象是整道题的核心也是三种解法的共同源头。DFS 本质上是递归遍历一个连通分量并计数BFS 是用队列遍历一个连通分量并计数并查集更是天生就是维护连通分量个数的数据结构。理解了这一层你就不只是在背沉没小岛的模板而是真正掌握了这一类二维网格连通性问题的底层模型。很多同学只背 DFS 一种答案就上考场遇到变体题——比如求最大岛屿面积、判断不同岛屿形状——就完全傻眼原因就是没把题目抽象到连通分量层面。记住一个套路和掌握一个模型差距就是在这类题上体现出来的。1.3 为什么机考爱考这道题站在出题人角度岛屿数量几乎是机考的完美题目。它题面简短不存在读懂题比做题还难的情况它存在多条解法路径能天然分层——写出 DFS 说明你懂递归写出 BFS 说明你熟悉队列写出并查集说明你数据结构功底扎实它又暗藏多个淘汰点输入格式、字符类型、边界判断、原地修改每一个都能刷掉一批人。从我参加过的模拟笔试和阅卷经历看二维网格遍历题在机考中属于常青树。它不像动态规划那样需要大量推导也不像字符串题那样 corner case 多到头皮发麻但能在短短二十分钟里同时考察循环控制、递归理解、复杂度意识和代码整洁度。对于准备机考的人来说把这道题当作二维网格系列的入口是最划算的投入——吃透它后面的岛屿周长、岛屿最大面积、被围绕的区域、不同岛屿数量全都能顺下来。2. 解法一DFS两分钟写出的标准答案2.1 沉没小岛的核心思路DFS 解法一句话概括遇到陆地就计数然后把这块陆地连同上下左右所有相连的陆地一起沉没成水之后继续扫描遇到下一块陆地就说明来到了新的岛屿再计数、再沉没。沉没这个动作是整段代码的灵魂。每当我们发现一块陆地就通过递归把所有和它连通的陆地全部改成 0这样后面主循环再扫到 1 时必然属于一个全新的岛屿。这个流程也叫 flood fill洪水填充是图形学里填充连通区域的标准算法画图软件里的油漆桶工具用的就是类似原理从一个种子点开始把颜色一致的连通区域全部换色。沉没操作有两种实现直接修改原网格或者单独开一个 visited 二维数组记录访问状态。直接修改省内存、写起来快坏处是改变了输入数据如果题目明确要求不能修改原数组或者你在本地调试时需要反复使用原始数据就得用 visited 数组。机考环境下我默认直接修改因为它代码最短出错概率最低。这正是机考和工程实践的一个差别工程里要尽量避免副作用机考里则要追求快速且正确。2.2 完整代码与逐行拆解def numIslands(grid): if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) count 0 def dfs(i, j): # 先判边界再判值越界或遇到水都直接返回 if i 0 or i rows or j 0 or j cols or grid[i][j] 0: return # 沉没当前格子避免重复访问 grid[i][j] 0 # 向四个方向递归扩张 dfs(i 1, j) dfs(i - 1, j) dfs(i, j 1) dfs(i, j - 1) for i in range(rows): for j in range(cols): if grid[i][j] 1: count 1 dfs(i, j) return count整段代码分三层最外层两层 for 循环负责扫描全图发现陆地时 count 加一并以这个格子为起点调用 dfsdfs 内部先判断边界和值然后把当前格改成 0再向上下左右递归。这里有一个必须理解清楚的细节主循环里的if grid[i][j] 1不是在数格子而是在发现新岛屿。因为每次 dfs 都会吞掉一整片连通的陆地所以当主循环再次遇到 1 时它必然是之前从未访问过的新岛屿的起点。如果你没想通这一层很容易写出在 dfs 里也计数的重复计数代码一个小网格就能把你绕晕。2.3 边界判断的顺序问题递归终止条件是这类二维题最容易出错的点。很多新手第一版代码长这样def dfs(i, j): if grid[i][j] 0: return grid[i][j] 0 dfs(i 1, j) ...一提交就报 IndexError。原因很简单访问grid[i][j]之前没有检查下标是否越界。当递归到网格边缘时i 可能等于 rows 或 j 可能等于 cols此时拿着越界下标直接索引必然崩溃。正确写法是把边界检查和值检查塞在同一个 if 里并且边界判断在前if i 0 or i rows or j 0 or j cols or grid[i][j] 0。Python 的 or 是短路求值前面的越界条件一旦成立后面的grid[i][j]根本不会执行所以这种写法是安全的。别小看这个顺序问题。它几乎贯穿所有二维网格递归题岛屿周长、矩阵最长递增路径、迷宫寻路全是同一个套路。你只要养成先边界、后取值的习惯这一整类题的鲁棒性都能提升一大截。3. 解法二BFS用队列避开递归爆栈3.1 队列式洪水填充DFS 靠系统递归栈BFS 则用显式队列。二者的高层思路完全一致遇到陆地就计数然后把整片岛屿沉没。区别只在于扩散顺序——DFS 一路走到黑再回头BFS 像水波一样一层一层向外扩散。BFS 的流程是发现陆地后把起点坐标加入队列并立刻标记成 0然后循环弹出队首元素检查它的上下左右四个邻居凡是陆地就标成 0 再入队队列清空时一整片岛屿就处理完了主循环继续找下一块新陆地。这里有一个贯穿整个 BFS 的重要原则入队即标记。也就是说某个格子一旦决定入队就要立刻把它改成已访问而不是等它出队时再改。否则同一个格子可能同时被两个邻居发现被重复入队队列里堆满冗余坐标严重时队列膨胀、程序超时甚至死循环。这一点我在给朋友辅导时几乎每次都要强调因为它的隐蔽性太强了小网格测试时问题不明显大网格一跑就露馅。3.2 完整代码与逐行拆解from collections import deque def numIslands(grid): if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) count 0 directions [(1, 0), (-1, 0), (0, 1), (0, -1)] for i in range(rows): for j in range(cols): if grid[i][j] 1: count 1 # 用队列做本岛扩散 queue deque([(i, j)]) grid[i][j] 0 while queue: x, y queue.popleft() for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: grid[nx][ny] 0 queue.append((nx, ny)) return count与 DFS 版本对比结构高度对称外层两层循环负责发现新岛内层 while 循环负责吞掉整座岛。真正的区别在方向处理上——DFS 用四次递归调用体现四个方向BFS 用 directions 数组加 for 循环批量处理。后者看起来更紧凑也为将来扩展到八连通方向留了口子只要往 directions 里多加四个元组就行。3.3 入队即标记最容易踩的暗坑我把这个坑单独拎出来细讲因为它值得。假设你写的是出队时标记while queue: x, y queue.popleft() if grid[x][y] 1: grid[x][y] 0 for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: queue.append((nx, ny))表面上看逻辑也对出队时先判断是不是 1是就沉没并扩散。问题在于两个相邻的陆地格子可能把同一个邻居先后入队两次第一次入队时邻居还是 1等它真的出队时它自己已经被标记成 0于是不会再扩散但队列里已经多存了一份坐标。网格一大这种重复入队会导致大量无效的弹出与判断队列里塞满冗余坐标白白浪费时间和内存如果连出队时的判断也漏写那就是彻底的死循环。正确的做法是入队即标记在我给的完整代码里就是grid[nx][ny] 0紧跟在判断之后、入队之前。这个细节在面试里经常被追问你能讲清楚为什么面试官就知道你是真写过 BFS而不是背的模板。4. 解法三并查集连通分量的本质4.1 从拉帮结派理解并查集DFS 和 BFS 都是一种主动的淹没式遍历并查集换了个角度先把每个陆地格子当成自己独立的小岛然后扫描整个网格把所有相邻的陆地合并到同一个集合里。合并一次集合数就减一。扫描结束后剩下的集合数就是岛屿数量。这个概念很像现实生活中的拉帮结派。最开始每个人都单打独斗每个人都自成圈子一旦发现两个人认识就把两个圈子合并等所有关系都处理完剩下的圈子总数就是答案。并查集这个数据结构就是为这种场景设计的核心只有两个操作find 查找某个元素属于哪个集合并做路径压缩加速union 合并两个集合顺便维护集合总数。在面试里用并查集解这道题属于典型的加分项。因为大部分考生只会 DFS你能写出并查集直接证明你理解连通分量的本质而不只是会套递归模板。但从实际机考策略看并查集的代码量和思维成本都比前两种高如果不是时间非常充裕我不建议把它作为考场的首选答案。4.2 完整代码与逐行拆解class UnionFind: def __init__(self): self.parent {} self.count 0 def add(self, x): if x not in self.parent: self.parent[x] x self.count 1 def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) # 路径压缩 return self.parent[x] def union(self, x, y): px, py self.find(x), self.find(y) if px py: return self.parent[py] px self.count - 1 def numIslands(grid): if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) uf UnionFind() for i in range(rows): for j in range(cols): if grid[i][j] 1: uf.add((i, j)) # 只向右和向下合并即可左边和上边的关系已被之前扫描处理 if i 0 and grid[i - 1][j] 1: uf.union((i, j), (i - 1, j)) if j 0 and grid[i][j - 1] 1: uf.union((i, j), (i, j - 1)) return uf.count这里的 UnionFind 用字典存父节点键是格子坐标元组好处是只需登记陆地格子不必给整张 m×n 网格预先分配数组。find 里做了路径压缩每次查找都会把路径上的节点直接挂到根节点下后续查找近乎 O(1)。union 合并两个不同集合时 count 减一这个 count 就是从始至终的连通分量个数。有几个实现细节值得留意。add 操作要放在合并之前保证当前格子的父节点先登记上只向右下两个方向做合并就足够因为左上方向的连接关系在更早的扫描中已经处理过四个方向全做也能得到正确答案但会带来大量冗余的 find 调用纯粹浪费。并查集解法不需要修改原网格这对某些要求输入不可变的场景非常友好。4.3 三种解法怎么选把三种解法放在一张表里对比取舍会非常清晰对比维度DFSBFS并查集时间复杂度O(mn)O(mn)O(mn·α(mn))空间复杂度O(mn) 递归栈O(mn) 队列O(mn) 父节点表代码量最少中等最多是否修改原数组是是否主要风险递归爆栈队列膨胀实现复杂度高时间复杂度里的 α 是反阿克曼函数增长极其缓慢实际使用中可以当成常数所以并查集在时间上也不输。空间上三种解法的上界都是 O(mn)差别主要在常数和实际占用。我的选择建议很明确。机考时间紧、想求稳默认写 DFS因为它最短写错的概率最低如果题目给的网格规模大比如 1000×1000 的全 1或者你判断自己的递归深度会吃紧果断换 BFS如果题目有后续不断新增陆地、每加一块都要返回当前岛屿数量这种动态需求DFS 和 BFS 都得全图重扫而并查集只要继续 union 就行这时候并查集就是唯一正解。5. 机考实战必须避开的五个坑5.1 输入读取与字符类型机考和 LeetCode 一个很大的差别是输入输出要自己处理。常见的输入格式有两种一种是第一行给出行数列数 m n接着给 m 行长度为 n 的连续字符串另一种是 m 行、每行 n 个以空格分隔的 0/1。无论哪种第一步都要小心行列顺序读反了后面全乱。我给你一个比较稳的读取模板import sys def main(): data sys.stdin.read().strip().split() if not data: return m, n int(data[0]), int(data[1]) rest data[2:] # 情形A连续字符串如 11010rest 长度 m # 情形B空格分隔的字符如 1 1 0 1 0rest 长度 m*n if len(rest) m: grid [list(line) for line in rest] else: grid [] for i in range(m): grid.append(rest[i * n:(i 1) * n]) print(numIslands(grid)) if __name__ __main__: main()用sys.stdin.read()一次性读入全部文本再按空白字符切分好处是同时兼容换行分隔和空格分隔。判断逻辑里始终用字符1、0不要在读取阶段把字符转成整数省得后面比较时又踩一遍字符和整数的坑。这里的分支判断可能有人觉得绕其实核心就是看数据被切成了一行一个整串还是每个字符独立成 token两种都兼容机考时就不用猜平台格式了。5.2 递归深度限制这是岛屿数量在机考里最阴险的杀手。LeetCode 的判题环境对用例尺度有设计递归 DFS 很少出问题但机考平台动不动就上 200×200 甚至 1000×1000 的全 1 网格纯递归 DFS 的调用链可能深达一万层以上。Python 默认递归深度上限是 1000直接抛 RecursionError。可以用sys.setrecursionlimit(1000000)临时调高上限但这只是治标。操作系统函数调用栈的大小是固定的递归层数达到几万层时照样会因为真正的栈空间耗尽而段错误而且在机考平台上这种错误往往显示成一段乱码排查体验极其痛苦。所以我的建议非常明确机考遇到这类网格题只要规模有可能超过 200×200默认写 BFS别去赌递归深度。考前把 BFS 模板默写两遍把它变成肌肉记忆。5.3 高频 Bug 速查表我把这些年见到的、自己踩过的坑整理成一张速查表症状可能原因解决办法结果一直是 0拿字符 1 和整数 1 比较统一用 1、0 字符串比较结果偏大每格都算一座岛沉没操作没生效漏写grid[i][j] 0进入递归或入队时立即标记报 IndexError访问格子前没做越界判断先判边界再访问grid[x][y]死循环或内存暴涨BFS 标记时机不对出队才标记改进入队即标记大网格直接崩溃递归深度超限换 BFS或调高递归深度限制第二行的坑我印象最深。早期写 DFS 时我试过把grid[i][j] 0放在递归调用之后结果相邻格子互相反复调用直接递归爆栈也试过漏掉这行标记导致同一片岛被主循环数了好几次输出明显偏大。这类 bug 最坑的地方在于小样例很难暴露因为网格小、重复访问概率低输出看起来好像没问题一上大数据就原形毕露。我的调试习惯是写完代码先在纸上画一个 3×3 的手工网格跟着代码走一遍流程两个来回下来大多数 bug 都能自己现形。5.4 复杂度该怎么答三种解法的时间复杂度都是 O(mn)m 是行数、n 是列数因为每个格子最多被处理常数次——主循环扫一遍dfs 或 bfs 过程中每个陆地格子处理一次。空间上DFS 最坏是 O(mn) 的递归栈全 1 网格下递归链可以很长BFS 队列最坏也能到 O(mn)并查集需要 O(mn) 存父节点表所以三种解法的空间上界都是 O(mn)。面试或机考复盘时几乎必被问复杂度。不要只背结论要能解释为什么每个格子只访问常数次。从主循环角度看扫描每个格子一次从沉没过程看每个格子一旦被标记成 0 就再也不会进入递归或入队分支所以整体工作量是每个格子常数次操作。这样答出来面试官才会觉得你是真懂而不是背了答案。6. 举一反三从岛屿数量到整个网格题家族6.1 岛屿最大面积695学完岛屿数量第一个推荐的变体是 695「岛屿的最大面积」。题目几乎一样只是把统计有多少座岛改成找出最大的那片有多大。思路很简单在沉没岛屿的同时用一个计数器统计当前连通分量里的格子数全局维护一个最大值最后输出。这个变体的训练价值在于它逼你学会边遍历边带返回值。DFS 版本需要把递归函数设计成返回当前连通分量的面积然后合并四个方向的返回结果。你会发现一旦真正理解了沉没逻辑加上返回值几乎不费力气而这个能力会在很多题目里反复用到比如树形 DP、矩阵路径问题。如果你做这题时觉得别扭大概率是岛屿数量的模板还没吃透回去再练。6.2 被围绕的区域130第二个变体是 130「被围绕的区域」它把问题反了过来把那些完全被水包围的陆地改成水。最稳的解法是先沿网格四条边界做 DFS 或 BFS把所有与边界相连的陆地先标记成另一种状态比如改成 A代表安全区然后全图扫描把剩下的 1 改成 0再把 A 改回 1。这个题真正的考点是反向思考。很多新手上来就试图在内部判断一个格子是否被水围住但二维网格里局部判断非常困难反过来从边界向内扩张先排除掉不会被围住的区域剩下的就都是要处理的。练这题的收获是建立逆向 flood fill的直觉这一招在封闭岛屿、边界扩散、区域染色等题目中都会用到。6.3 不同岛屿数量694再深一层694「不同岛屿的数量」要求统计形状不重复的岛屿。做法是在 DFS 过程中记录遍历路径的方向序列比如用字符串记录每一步走的是上、下、左、右最后把这些轨迹放到集合里去重数量就是不同形状的岛屿数。这题有个经典小坑如果只记录前进方向而不记录回溯方向两个中心对称的形状会被误判成同一种。正确的做法是把递归出栈回溯时的反向移动也记录下来这样每个形状对应唯一的遍历轨迹。第一次做的时候踩一次这个坑印象会非常深以后遇到序列化、哈希计算类题目都会多留一个心眼。把这三个变体串起来看你会发现它们的内核都是岛屿数量那道题连通分量、flood fill、DFS 与 BFS 的选择。每练一个变体都是在同一个模型上叠加新技能而不是孤立刷题。这也正是我反复强调吃透经典题的原因——一道题的价值从来不只是它本身。最后分享一点个人体会。我最早刷这道题时也走过弯路直接看答案、背模板、提交通过以为自己会了结果两周后重做一遍居然连边界判断都写错。后来我换了个笨办法花了一个晚上把 DFS 和 BFS 各独立写三遍再手写并查集最后故意制造几个 bug 来观察报错特征。这个过程确实慢但它让我彻底记住了这道题的所有关键细节。如果你正在准备机考真的建议别急着背答案先独立写一遍 DFS再改成 BFS再碰变体题。等你哪天能不看任何参考十分钟内把三种解法都写出来这道题才算真正毕业。 LeetCode 200岛屿数量：DFS、BFS与并查集三解全析
机考刷题系列这一期落到一道绕不开的经典题LeetCode 200「岛屿数量」。只要是参加过机考或者准备过算法面试的人几乎都撞见过这道题。它题面短、理解门槛低但背后同时牵出 DFS、BFS、并查集三条技术路线而且处处是坑字符和数字的混淆、递归深度、边界越界、标记时机……任何一个点都能让你在考场上白丢一道题的分。一句话概括题目给一个由 1 和 0 组成的二维网格1 代表陆地0 代表水上下左右相邻的陆地属于同一座岛屿统计网格里岛屿的总数。就这么简单但恰恰是这种看起来简单的题最能区分出真会写代码的人和只会背模板的人。这篇文章围绕这道题把三种主流解法全部拆开结合机考场景讲清楚每一步为什么要这么写、有哪些坑、变体题怎么练。适合读这篇文章的人有三类正在准备机考的应届生想系统补图遍历基础的开发者以及那些刷过题但只记住了答案、没搞懂原理的背题党。如果你属于最后一类建议跟着代码自己敲一遍重点看我标注原因的部分收获会完全不一样。1. 题面拆解岛屿数量究竟在考什么1.1 原题回顾与输入输出约定先回顾原题。给定一个 m 行 n 列的二维网格 grid每个格子是字符 1陆地或 0水。要求计算岛屿数量其中岛屿由水平或垂直方向上相邻的陆地连片构成并假设网格四条边之外都是水。两个输入样例能帮你快速建立直觉。第一个样例11110 11010 11000 00000输出是 1因为所有陆地连成了一整片中间的水洼并没有把岛屿切开。第二个样例11000 11000 00100 00011输出是 3左上角一块、中间孤立一块、右下角一块。这题有两个约定特别容易被忽略。第一格子是字符 1 和 0不是整数 1 和 0。新手写判断时经常图省事写grid[i][j] 1在 Python 里字符和整数永远不相等于是整个计数全是 0而且由于逻辑上看不出毛病这种 bug 极难自查。第二相邻只算上下左右四个方向斜对角不算。这个规则把问题定位成四连通比图像分割里的八连通简单一档但如果刚做完棋盘、图像类的题很容易惯性把对角线也算进去导致本应分开的岛屿被合并成一座答案偏小。1.2 从数岛屿到数连通分量如果不做抽象你看到的就是一个装满 0 和 1 的表格数起来全凭感觉。但把它转成图论视角后思路会豁然开朗把每个 1 格子看成图里的一个节点把相邻陆地之间的邻接关系看成边那么一座岛屿就是一个连通分量题目要求的岛屿数量就等于整个网格图中连通分量的个数。这个抽象是整道题的核心也是三种解法的共同源头。DFS 本质上是递归遍历一个连通分量并计数BFS 是用队列遍历一个连通分量并计数并查集更是天生就是维护连通分量个数的数据结构。理解了这一层你就不只是在背沉没小岛的模板而是真正掌握了这一类二维网格连通性问题的底层模型。很多同学只背 DFS 一种答案就上考场遇到变体题——比如求最大岛屿面积、判断不同岛屿形状——就完全傻眼原因就是没把题目抽象到连通分量层面。记住一个套路和掌握一个模型差距就是在这类题上体现出来的。1.3 为什么机考爱考这道题站在出题人角度岛屿数量几乎是机考的完美题目。它题面简短不存在读懂题比做题还难的情况它存在多条解法路径能天然分层——写出 DFS 说明你懂递归写出 BFS 说明你熟悉队列写出并查集说明你数据结构功底扎实它又暗藏多个淘汰点输入格式、字符类型、边界判断、原地修改每一个都能刷掉一批人。从我参加过的模拟笔试和阅卷经历看二维网格遍历题在机考中属于常青树。它不像动态规划那样需要大量推导也不像字符串题那样 corner case 多到头皮发麻但能在短短二十分钟里同时考察循环控制、递归理解、复杂度意识和代码整洁度。对于准备机考的人来说把这道题当作二维网格系列的入口是最划算的投入——吃透它后面的岛屿周长、岛屿最大面积、被围绕的区域、不同岛屿数量全都能顺下来。2. 解法一DFS两分钟写出的标准答案2.1 沉没小岛的核心思路DFS 解法一句话概括遇到陆地就计数然后把这块陆地连同上下左右所有相连的陆地一起沉没成水之后继续扫描遇到下一块陆地就说明来到了新的岛屿再计数、再沉没。沉没这个动作是整段代码的灵魂。每当我们发现一块陆地就通过递归把所有和它连通的陆地全部改成 0这样后面主循环再扫到 1 时必然属于一个全新的岛屿。这个流程也叫 flood fill洪水填充是图形学里填充连通区域的标准算法画图软件里的油漆桶工具用的就是类似原理从一个种子点开始把颜色一致的连通区域全部换色。沉没操作有两种实现直接修改原网格或者单独开一个 visited 二维数组记录访问状态。直接修改省内存、写起来快坏处是改变了输入数据如果题目明确要求不能修改原数组或者你在本地调试时需要反复使用原始数据就得用 visited 数组。机考环境下我默认直接修改因为它代码最短出错概率最低。这正是机考和工程实践的一个差别工程里要尽量避免副作用机考里则要追求快速且正确。2.2 完整代码与逐行拆解def numIslands(grid): if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) count 0 def dfs(i, j): # 先判边界再判值越界或遇到水都直接返回 if i 0 or i rows or j 0 or j cols or grid[i][j] 0: return # 沉没当前格子避免重复访问 grid[i][j] 0 # 向四个方向递归扩张 dfs(i 1, j) dfs(i - 1, j) dfs(i, j 1) dfs(i, j - 1) for i in range(rows): for j in range(cols): if grid[i][j] 1: count 1 dfs(i, j) return count整段代码分三层最外层两层 for 循环负责扫描全图发现陆地时 count 加一并以这个格子为起点调用 dfsdfs 内部先判断边界和值然后把当前格改成 0再向上下左右递归。这里有一个必须理解清楚的细节主循环里的if grid[i][j] 1不是在数格子而是在发现新岛屿。因为每次 dfs 都会吞掉一整片连通的陆地所以当主循环再次遇到 1 时它必然是之前从未访问过的新岛屿的起点。如果你没想通这一层很容易写出在 dfs 里也计数的重复计数代码一个小网格就能把你绕晕。2.3 边界判断的顺序问题递归终止条件是这类二维题最容易出错的点。很多新手第一版代码长这样def dfs(i, j): if grid[i][j] 0: return grid[i][j] 0 dfs(i 1, j) ...一提交就报 IndexError。原因很简单访问grid[i][j]之前没有检查下标是否越界。当递归到网格边缘时i 可能等于 rows 或 j 可能等于 cols此时拿着越界下标直接索引必然崩溃。正确写法是把边界检查和值检查塞在同一个 if 里并且边界判断在前if i 0 or i rows or j 0 or j cols or grid[i][j] 0。Python 的 or 是短路求值前面的越界条件一旦成立后面的grid[i][j]根本不会执行所以这种写法是安全的。别小看这个顺序问题。它几乎贯穿所有二维网格递归题岛屿周长、矩阵最长递增路径、迷宫寻路全是同一个套路。你只要养成先边界、后取值的习惯这一整类题的鲁棒性都能提升一大截。3. 解法二BFS用队列避开递归爆栈3.1 队列式洪水填充DFS 靠系统递归栈BFS 则用显式队列。二者的高层思路完全一致遇到陆地就计数然后把整片岛屿沉没。区别只在于扩散顺序——DFS 一路走到黑再回头BFS 像水波一样一层一层向外扩散。BFS 的流程是发现陆地后把起点坐标加入队列并立刻标记成 0然后循环弹出队首元素检查它的上下左右四个邻居凡是陆地就标成 0 再入队队列清空时一整片岛屿就处理完了主循环继续找下一块新陆地。这里有一个贯穿整个 BFS 的重要原则入队即标记。也就是说某个格子一旦决定入队就要立刻把它改成已访问而不是等它出队时再改。否则同一个格子可能同时被两个邻居发现被重复入队队列里堆满冗余坐标严重时队列膨胀、程序超时甚至死循环。这一点我在给朋友辅导时几乎每次都要强调因为它的隐蔽性太强了小网格测试时问题不明显大网格一跑就露馅。3.2 完整代码与逐行拆解from collections import deque def numIslands(grid): if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) count 0 directions [(1, 0), (-1, 0), (0, 1), (0, -1)] for i in range(rows): for j in range(cols): if grid[i][j] 1: count 1 # 用队列做本岛扩散 queue deque([(i, j)]) grid[i][j] 0 while queue: x, y queue.popleft() for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: grid[nx][ny] 0 queue.append((nx, ny)) return count与 DFS 版本对比结构高度对称外层两层循环负责发现新岛内层 while 循环负责吞掉整座岛。真正的区别在方向处理上——DFS 用四次递归调用体现四个方向BFS 用 directions 数组加 for 循环批量处理。后者看起来更紧凑也为将来扩展到八连通方向留了口子只要往 directions 里多加四个元组就行。3.3 入队即标记最容易踩的暗坑我把这个坑单独拎出来细讲因为它值得。假设你写的是出队时标记while queue: x, y queue.popleft() if grid[x][y] 1: grid[x][y] 0 for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: queue.append((nx, ny))表面上看逻辑也对出队时先判断是不是 1是就沉没并扩散。问题在于两个相邻的陆地格子可能把同一个邻居先后入队两次第一次入队时邻居还是 1等它真的出队时它自己已经被标记成 0于是不会再扩散但队列里已经多存了一份坐标。网格一大这种重复入队会导致大量无效的弹出与判断队列里塞满冗余坐标白白浪费时间和内存如果连出队时的判断也漏写那就是彻底的死循环。正确的做法是入队即标记在我给的完整代码里就是grid[nx][ny] 0紧跟在判断之后、入队之前。这个细节在面试里经常被追问你能讲清楚为什么面试官就知道你是真写过 BFS而不是背的模板。4. 解法三并查集连通分量的本质4.1 从拉帮结派理解并查集DFS 和 BFS 都是一种主动的淹没式遍历并查集换了个角度先把每个陆地格子当成自己独立的小岛然后扫描整个网格把所有相邻的陆地合并到同一个集合里。合并一次集合数就减一。扫描结束后剩下的集合数就是岛屿数量。这个概念很像现实生活中的拉帮结派。最开始每个人都单打独斗每个人都自成圈子一旦发现两个人认识就把两个圈子合并等所有关系都处理完剩下的圈子总数就是答案。并查集这个数据结构就是为这种场景设计的核心只有两个操作find 查找某个元素属于哪个集合并做路径压缩加速union 合并两个集合顺便维护集合总数。在面试里用并查集解这道题属于典型的加分项。因为大部分考生只会 DFS你能写出并查集直接证明你理解连通分量的本质而不只是会套递归模板。但从实际机考策略看并查集的代码量和思维成本都比前两种高如果不是时间非常充裕我不建议把它作为考场的首选答案。4.2 完整代码与逐行拆解class UnionFind: def __init__(self): self.parent {} self.count 0 def add(self, x): if x not in self.parent: self.parent[x] x self.count 1 def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) # 路径压缩 return self.parent[x] def union(self, x, y): px, py self.find(x), self.find(y) if px py: return self.parent[py] px self.count - 1 def numIslands(grid): if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) uf UnionFind() for i in range(rows): for j in range(cols): if grid[i][j] 1: uf.add((i, j)) # 只向右和向下合并即可左边和上边的关系已被之前扫描处理 if i 0 and grid[i - 1][j] 1: uf.union((i, j), (i - 1, j)) if j 0 and grid[i][j - 1] 1: uf.union((i, j), (i, j - 1)) return uf.count这里的 UnionFind 用字典存父节点键是格子坐标元组好处是只需登记陆地格子不必给整张 m×n 网格预先分配数组。find 里做了路径压缩每次查找都会把路径上的节点直接挂到根节点下后续查找近乎 O(1)。union 合并两个不同集合时 count 减一这个 count 就是从始至终的连通分量个数。有几个实现细节值得留意。add 操作要放在合并之前保证当前格子的父节点先登记上只向右下两个方向做合并就足够因为左上方向的连接关系在更早的扫描中已经处理过四个方向全做也能得到正确答案但会带来大量冗余的 find 调用纯粹浪费。并查集解法不需要修改原网格这对某些要求输入不可变的场景非常友好。4.3 三种解法怎么选把三种解法放在一张表里对比取舍会非常清晰对比维度DFSBFS并查集时间复杂度O(mn)O(mn)O(mn·α(mn))空间复杂度O(mn) 递归栈O(mn) 队列O(mn) 父节点表代码量最少中等最多是否修改原数组是是否主要风险递归爆栈队列膨胀实现复杂度高时间复杂度里的 α 是反阿克曼函数增长极其缓慢实际使用中可以当成常数所以并查集在时间上也不输。空间上三种解法的上界都是 O(mn)差别主要在常数和实际占用。我的选择建议很明确。机考时间紧、想求稳默认写 DFS因为它最短写错的概率最低如果题目给的网格规模大比如 1000×1000 的全 1或者你判断自己的递归深度会吃紧果断换 BFS如果题目有后续不断新增陆地、每加一块都要返回当前岛屿数量这种动态需求DFS 和 BFS 都得全图重扫而并查集只要继续 union 就行这时候并查集就是唯一正解。5. 机考实战必须避开的五个坑5.1 输入读取与字符类型机考和 LeetCode 一个很大的差别是输入输出要自己处理。常见的输入格式有两种一种是第一行给出行数列数 m n接着给 m 行长度为 n 的连续字符串另一种是 m 行、每行 n 个以空格分隔的 0/1。无论哪种第一步都要小心行列顺序读反了后面全乱。我给你一个比较稳的读取模板import sys def main(): data sys.stdin.read().strip().split() if not data: return m, n int(data[0]), int(data[1]) rest data[2:] # 情形A连续字符串如 11010rest 长度 m # 情形B空格分隔的字符如 1 1 0 1 0rest 长度 m*n if len(rest) m: grid [list(line) for line in rest] else: grid [] for i in range(m): grid.append(rest[i * n:(i 1) * n]) print(numIslands(grid)) if __name__ __main__: main()用sys.stdin.read()一次性读入全部文本再按空白字符切分好处是同时兼容换行分隔和空格分隔。判断逻辑里始终用字符1、0不要在读取阶段把字符转成整数省得后面比较时又踩一遍字符和整数的坑。这里的分支判断可能有人觉得绕其实核心就是看数据被切成了一行一个整串还是每个字符独立成 token两种都兼容机考时就不用猜平台格式了。5.2 递归深度限制这是岛屿数量在机考里最阴险的杀手。LeetCode 的判题环境对用例尺度有设计递归 DFS 很少出问题但机考平台动不动就上 200×200 甚至 1000×1000 的全 1 网格纯递归 DFS 的调用链可能深达一万层以上。Python 默认递归深度上限是 1000直接抛 RecursionError。可以用sys.setrecursionlimit(1000000)临时调高上限但这只是治标。操作系统函数调用栈的大小是固定的递归层数达到几万层时照样会因为真正的栈空间耗尽而段错误而且在机考平台上这种错误往往显示成一段乱码排查体验极其痛苦。所以我的建议非常明确机考遇到这类网格题只要规模有可能超过 200×200默认写 BFS别去赌递归深度。考前把 BFS 模板默写两遍把它变成肌肉记忆。5.3 高频 Bug 速查表我把这些年见到的、自己踩过的坑整理成一张速查表症状可能原因解决办法结果一直是 0拿字符 1 和整数 1 比较统一用 1、0 字符串比较结果偏大每格都算一座岛沉没操作没生效漏写grid[i][j] 0进入递归或入队时立即标记报 IndexError访问格子前没做越界判断先判边界再访问grid[x][y]死循环或内存暴涨BFS 标记时机不对出队才标记改进入队即标记大网格直接崩溃递归深度超限换 BFS或调高递归深度限制第二行的坑我印象最深。早期写 DFS 时我试过把grid[i][j] 0放在递归调用之后结果相邻格子互相反复调用直接递归爆栈也试过漏掉这行标记导致同一片岛被主循环数了好几次输出明显偏大。这类 bug 最坑的地方在于小样例很难暴露因为网格小、重复访问概率低输出看起来好像没问题一上大数据就原形毕露。我的调试习惯是写完代码先在纸上画一个 3×3 的手工网格跟着代码走一遍流程两个来回下来大多数 bug 都能自己现形。5.4 复杂度该怎么答三种解法的时间复杂度都是 O(mn)m 是行数、n 是列数因为每个格子最多被处理常数次——主循环扫一遍dfs 或 bfs 过程中每个陆地格子处理一次。空间上DFS 最坏是 O(mn) 的递归栈全 1 网格下递归链可以很长BFS 队列最坏也能到 O(mn)并查集需要 O(mn) 存父节点表所以三种解法的空间上界都是 O(mn)。面试或机考复盘时几乎必被问复杂度。不要只背结论要能解释为什么每个格子只访问常数次。从主循环角度看扫描每个格子一次从沉没过程看每个格子一旦被标记成 0 就再也不会进入递归或入队分支所以整体工作量是每个格子常数次操作。这样答出来面试官才会觉得你是真懂而不是背了答案。6. 举一反三从岛屿数量到整个网格题家族6.1 岛屿最大面积695学完岛屿数量第一个推荐的变体是 695「岛屿的最大面积」。题目几乎一样只是把统计有多少座岛改成找出最大的那片有多大。思路很简单在沉没岛屿的同时用一个计数器统计当前连通分量里的格子数全局维护一个最大值最后输出。这个变体的训练价值在于它逼你学会边遍历边带返回值。DFS 版本需要把递归函数设计成返回当前连通分量的面积然后合并四个方向的返回结果。你会发现一旦真正理解了沉没逻辑加上返回值几乎不费力气而这个能力会在很多题目里反复用到比如树形 DP、矩阵路径问题。如果你做这题时觉得别扭大概率是岛屿数量的模板还没吃透回去再练。6.2 被围绕的区域130第二个变体是 130「被围绕的区域」它把问题反了过来把那些完全被水包围的陆地改成水。最稳的解法是先沿网格四条边界做 DFS 或 BFS把所有与边界相连的陆地先标记成另一种状态比如改成 A代表安全区然后全图扫描把剩下的 1 改成 0再把 A 改回 1。这个题真正的考点是反向思考。很多新手上来就试图在内部判断一个格子是否被水围住但二维网格里局部判断非常困难反过来从边界向内扩张先排除掉不会被围住的区域剩下的就都是要处理的。练这题的收获是建立逆向 flood fill的直觉这一招在封闭岛屿、边界扩散、区域染色等题目中都会用到。6.3 不同岛屿数量694再深一层694「不同岛屿的数量」要求统计形状不重复的岛屿。做法是在 DFS 过程中记录遍历路径的方向序列比如用字符串记录每一步走的是上、下、左、右最后把这些轨迹放到集合里去重数量就是不同形状的岛屿数。这题有个经典小坑如果只记录前进方向而不记录回溯方向两个中心对称的形状会被误判成同一种。正确的做法是把递归出栈回溯时的反向移动也记录下来这样每个形状对应唯一的遍历轨迹。第一次做的时候踩一次这个坑印象会非常深以后遇到序列化、哈希计算类题目都会多留一个心眼。把这三个变体串起来看你会发现它们的内核都是岛屿数量那道题连通分量、flood fill、DFS 与 BFS 的选择。每练一个变体都是在同一个模型上叠加新技能而不是孤立刷题。这也正是我反复强调吃透经典题的原因——一道题的价值从来不只是它本身。最后分享一点个人体会。我最早刷这道题时也走过弯路直接看答案、背模板、提交通过以为自己会了结果两周后重做一遍居然连边界判断都写错。后来我换了个笨办法花了一个晚上把 DFS 和 BFS 各独立写三遍再手写并查集最后故意制造几个 bug 来观察报错特征。这个过程确实慢但它让我彻底记住了这道题的所有关键细节。如果你正在准备机考真的建议别急着背答案先独立写一遍 DFS再改成 BFS再碰变体题。等你哪天能不看任何参考十分钟内把三种解法都写出来这道题才算真正毕业。