LeetCode 463这道题我在刷题列表里放了很久一直觉得它属于那种“看一眼就会根本不需要专门写一篇博客”的简单题。直到上周给一个学弟讲这道岛屿的周长我才发现很多人第一次做的时候都会在同一个地方绕弯明明是每个陆地格子都有四条边为什么一个个加下来答案偏偏不对如果你也曾在这个问题上卡过壳或者只是想确认自己的写法是不是最优这篇应该能帮到你。我会把遍历计数和DFS两种主要做法都过一遍再补上一些我在实际刷题和面试陪练中总结的边界条件与坑。1. 这道题到底在考什么网格遍历的基础思维1.1 把周长问题翻译成代码语言题面本身非常短给你一个m x n的二维网格1表示陆地0表示水域整个网格里只有一个岛屿或者说题目保证陆地是连成一片的岛屿的四周都被水包围。让你返回这个岛屿的周长。很多人第一反应是数一数有多少个1然后乘以 4。这个思路只对完全孤立的单格陆地成立。一旦两块陆地挨在一起它们中间那条边就不再是“岛屿的外部边界”而是内部接缝。周长统计的本质是数“陆地与水交界”的边以及“陆地与网格边界”的边。所以在代码里我们要处理的实际上是两个问题怎么遍历整个二维网格怎么判断一条边算不算周长。判断逻辑也很固定从某个陆地格子出发向上下左右看如果邻居越界了说明这条边暴露在网格外面算周长如果邻居是水也算周长如果邻居是陆地这条边是内部边不算。我见过不少新手一上来就套 BFS/DFS 的模板结果把自己绕晕。其实这道题更重要的是一种“逐格判断”的建模能力把空间上的“边界”转化为代码里的“邻居判断”。1.2 为什么“每个陆地都加4”会算错直接加4的错误在于把内部共享边重复计算了。举个例子两个格子横着挨在一起[1][1]左边格子算 4 条边右边格子算 4 条边加起来是 8。但这两个格子组成的形状是一个 1x2 长方形它的真实周长是 6——上下左右四条边加上左右两端各一条总共 6。多出来的 2恰好就是中间那条共享边被左右两个格子各算了一次。把这个问题推广到一个大一点的岛屿你就会发现每有一对相邻的陆地格子就会多算 2 条内部边。所以正确的思路很简单周长 陆地格子数 × 4 - 相邻陆地对数 × 2这个公式就是 LeetCode 463 最经典的“加4减2”解法。理解了这个公式你再看任何题解都会觉得通透因为后面所有写法都是在实现这个公式。2. 遍历计数法加4减2为什么是这么写的2.1 只检查上方和左侧是因为一份边只数一次实现这个公式最简单的办法是遍历整个网格遇到陆地格子就先把4加上然后看它的上方和左方是否也是陆地如果是就减掉2。那为什么只检查上方和左侧不检查右边和下面因为遍历顺序是从上到下、从左到右。当你遍历到某个格子时它的上方和左方一定已经处理过了而它的右边和下方会在之后的遍历中轮到。如果当前格子检查了右边等遍历到右边那个格子时它又会检查自己的左边同一条共享边就被扣了两次。为了确保“每对相邻陆地只被统计一次”我只看两个方向就够了。这也解释了为什么这种方法不需要额外的visited数组它不是从某个点向外扩散而是把每个格子当成独立的检查点每对相邻关系只会被后出现的那个格子处理。2.2 加4减2的Python实现下面这段代码是网上流传最广、也最值得记住的版本from typing import List class Solution: def islandPerimeter(self, grid: List[List[int]]) - int: if not grid: return 0 rows, cols len(grid), len(grid[0]) ans 0 for r in range(rows): for c in range(cols): if grid[r][c] 1: ans 4 # 向左看是否也是陆地 if r 0 and grid[r - 1][c] 1: ans - 2 # 向上看是否也是陆地 if c 0 and grid[r][c - 1] 1: ans - 2 return ans核心就三行加4、判断上方、判断左方。很多题解里会写成检查grid[r-1][c]和grid[r][c-1]这个方向不要搞错。有同学会问如果输入是List[List[str]]里面存的是字符1和0怎么办很简单把grid[r][c] 1换成grid[r][c] 1然后比较对象也换成字符串即可。这类小变形在面试里经常出现。2.3 拿示例手动算一遍用题目自带的示例grid [ [0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0], [1, 1, 0, 0] ]陆地格子一共有 7 个7 × 4 28。再数相邻陆地对数。水平方向第2行的[1,1,1]有 2 对第4行的[1,1]有 1 对总共 3 对垂直方向第1列上下两组、第2列上下两组、第3列上下两组等一下这里要仔细看(1,1)和(0,1)相邻(1,1)和(2,1)相邻(2,1)和(3,1)相邻所以垂直方向也是 3 对。水平 3 对垂直 3 对一共 6 对。最终周长28 - 2 × 6 16。看到没有整个过程其实就是“每多一对相邻陆地周长少 2”。所以代码里用- 2而不是- 1原因就在这里。3. DFS数边界换个视角理解周长3.1 从哪个格子进怎么保证不漏不重遍历计数法很直接但很多人的第一反应还是 DFS毕竟一看到“岛屿”两个字就容易联想到连通块搜索。DFS 的思路也不复杂随便找一块陆地出发沿着陆地一路逛完整个岛屿每走到一个新格子就检查它的四周把暴露在外面的边加起来。这里有一个关键点什么时候算周长在 DFS 的每一步里我们对当前格子的四个方向做判断越界说明这条边是网格的外边界周长加 1碰到水0说明这条边是海岸线周长加 1碰到已经访问过的陆地跳过碰到未访问的陆地递归进去继续走。只要把访问标记做对每个陆地格子恰好被处理一次每条外部边也恰好被数到一次。3.2 递归出口越界和水都算周长递归版的代码长这样from typing import List class Solution: def islandPerimeter(self, grid: List[List[int]]) - int: if not grid: return 0 rows, cols len(grid), len(grid[0]) visited [[False] * cols for _ in range(rows)] ans 0 def dfs(r: int, c: int) - None: nonlocal ans visited[r][c] True for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc r dr, c dc if nr 0 or nr rows or nc 0 or nc cols: ans 1 elif grid[nr][nc] 0: ans 1 elif not visited[nr][nc]: dfs(nr, nc) for r in range(rows): for c in range(cols): if grid[r][c] 1 and not visited[r][c]: dfs(r, c) return ans注意两个细节。第一Python 的嵌套函数里如果要在内层修改外层变量ans必须写上nonlocal ans否则会报UnboundLocalError。很多人第一次写都会在这里卡一下。第二visited一定要在进入格子时立刻标记而不是在递归调用前才标记。如果你在递归调用时只标记了当前分支可能出现同一个格子被多个方向重复入栈的情况导致周长被重复统计。3.3 迭代DFS版本防止递归爆栈递归版的优点是代码直观缺点也很明显如果输入网格很大或者岛屿的形状是一条很长的蛇形递归深度会逼近陆地格子总数。Python 默认递归深度大约在 1000 左右一旦超过就会抛RecursionError。这种时候可以用显式栈来模拟 DFS思路完全一样from typing import List class Solution: def islandPerimeter(self, grid: List[List[int]]) - int: if not grid: return 0 rows, cols len(grid), len(grid[0]) visited set() stack [] ans 0 for r in range(rows): for c in range(cols): if grid[r][c] 1 and (r, c) not in visited: stack.append((r, c)) visited.add((r, c)) while stack: x, y stack.pop() for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)): nx, ny x dx, y dy if nx 0 or nx rows or ny 0 or ny cols: ans 1 elif grid[nx][ny] 0: ans 1 elif (nx, ny) not in visited: visited.add((nx, ny)) stack.append((nx, ny)) return ans这个版本不需要担心递归深度而且在区分多个岛屿的场景下依然成立。唯一的代价是多了一个visitedset空间复杂度从 O(1) 变成了 O(mn)。4. 最容易翻车的边界条件动手写之前先过一遍4.1 空网格、null输入、单行单列我在给学弟讲题的时候发现代码写出来能跑通示例的人不少但能一次性扛住所有边界用例的人不多。最常见的翻车点就是if not grid这个判空。如果输入是[]你直接访问grid[0]就会IndexError如果输入是Nonelen(grid)也会报错。所以任何解法开头都应该先写一句if not grid: return 0接下来是单行和单列的输入。比如grid [[1, 1, 1]]三个格子横着排中间两个邻居对周长应该是 8。遍历计数法里第一个格子没有上方和左方不减第二个格子左方是陆地减 2第三个格子左方是陆地减 2。整个过程没有任何数组越界风险因为我们判断条件里写了r 0和c 0。单列同理。这个条件顺序不能写成grid[r-1][c] 1 and r 0Python 短路求值虽然不会真的访问越界但可读性差也容易让面试官皱眉。4.2 我整理的最小用例集如果你在本地练习建议准备下面这组用例。它们能覆盖绝大多数实现错误输入期望周长说明[]0空网格什么都不存在None0需要判空[[1]]4单格岛屿四边都暴露[[1, 1, 1]]8一行三个陆地两个内部相邻对[[1], [1]]6竖着相邻两格共享一条边[[1, 1], [1, 1]]82x2 全陆地外框就是周长[[1, 0, 1], [1, 1, 1]]12凹形岛屿容易漏数的形状[[1, 0], [0, 1]]8两个分离陆地互不影响你可以把这些输入挨个跑一遍。如果某种写法在这些用例上全部通过再去提交 LeetCode 基本不会出问题。4.3 调试技巧把网格画出来我在调这类网格题时有个习惯在 DFS 里临时把访问过的格子改成2然后每次递归后用两层循环把二维状态打印出来。这样肉眼看一遍就能发现哪个方向漏数了、哪个方向重复计数了。比如想把 DFS 过程可视化可以在dfs函数的末尾临时加一段for row in visited: print( .join(* if v else . for v in row)) print(---)把visited中的布尔值映射成*和.配合原始网格里的0/1一眼就能确认当前已经走了哪些格子、还有哪些边界没数到。这种“画出来”的方法比盯着调试器有效率得多。5. 复杂度对比与面试现场的决策逻辑5.1 两种方案的时间和空间复杂度把这几种写法放在一起对比你能看得很清楚解法时间复杂度空间复杂度适用场景遍历计数加4减2O(mn)O(1)面试首选实现最简洁四方向探测遍历O(mn)O(1)思路最直观适合口述递归 DFSO(mn)O(mn) 递归栈练习递归或需要区分岛屿时迭代栈 DFSO(mn)O(mn)输入规模大、担心爆栈时间复杂度都是 O(mn)因为无论哪种做法每个格子至少要看一次。空间上遍历计数法是绝对的赢家不需要visited不需要递归栈常量级额外空间。这里多说一句面试时如果你能先说出“这道题 O(mn) 是下界因为每个格子至少要读一次”会比直接甩代码显得有深度得多。5.2 面试官会追问的三个变形我陪练过不少模拟面试LeetCode 463 作为简单题经常被当成“热身题”来问随后面试官会加戏。最常见的追问有三个。追问一如果网格里有多个岛屿返回总周长。遍历计数法不需要改任何代码因为它统计的是所有陆地格子的相邻关系跟连通性无关。DFS 版本需要把主循环里的调用从“只调用一次”改成“遍历所有未访问的陆地都调用一次”上面的递归版和栈版代码本来就支持这个逻辑。追问二如果要求返回每个岛屿各自的周长。这时候遍历计数法就没法直接用了因为它是全局统计。DFS 是更好的选择每次从新岛屿入口调用dfs得到的累加值就是这个岛屿的周长把结果存到列表里返回即可。追问三把int二维数组换成char二维数组。比较对象从1换成1其他逻辑完全不变。这个小变形主要考察你有没有真正理解代码而不是背模板。5.3 刷题时怎么选写法我的建议是面试第一遍先讲“加4减2”的思路手写用遍历计数法因为它代码短、不容易出错如果面试官追问 DFS再切换到递归版同时主动提一句“递归有爆栈风险大规模输入可以改成显式栈”。这样既展示了你会多种解法又表现出你对边界和工程风险的敏感性。6. 从463延伸开去网格遍历题的通用解题模板6.1 方向数组和visited是网格题的通用骨架刷题刷到一定量你会发现网格类题目的代码骨架高度相似一个方向数组通常写成((1,0), (-1,0), (0,1), (0,-1))一个visited集合或二维数组一组越界判断一个主循环负责遍历所有格子。LeetCode 463 虽然用遍历计数法不需要这些但 DFS 版本仍然遵循这个骨架。所以我建议你至少要把 DFS 版本写一遍不是为了这道题本身而是为了把网格搜索的手感练出来。把这个骨架背熟之后你会发现 LeetCode 200 岛屿数量、LeetCode 994 腐烂的橘子、LeetCode 130 被围绕的区域全都是在同一个框架上改统计逻辑或者传播规则。区别只在于200 数的是连通块个数遇到新的未访问陆地就计数并标记整个岛屿994 用多源 BFS 记录传播轮数130 从边界往内反推。把这些题放在一起对比着刷比一个个孤立地刷效果好得多。6.2 一道题串起一类题边界统计的通用思维回到 463 本身它真正想训练你的其实是“把二维空间关系翻译成逐格判断”这个动作。一次遍历、一个方向检查、一次减法背后对应的是边界如何定义、共享边如何避免重复计数。我自己在实际写代码时遇到跟边界有关的业务需求比如计算某个连通区域的外轮廓、统计行政区划之间的公共边界长度脑子里都会浮现这道题的模型。这也是为什么我一直觉得 LeetCode 刷题的意义不在于记住某道题的答案而在于把抽象的几何关系训练成条件反射。如果你也是刚开始刷网格类题目建议把 463 作为第一道入门题。它比 200 岛屿数量简单但又包含了方向判断、访问标记、边界处理这些最核心的要素它也比 994 腐烂的橘子更适合作为起点因为不需要理解 BFS 的层级扩散。先把这道题吃透再把 DFS 版本默写三遍后面遇到再复杂的网格题你都会觉得顺手很多。个人刷到这里的体会是简单题往往最见基本功。463 的标签是“简单”但它值得你多花一点时间把每一种解法都跑一遍把每一个为什么都想清楚。这样再遇到类似题目你就能少踩很多坑。