更新题目 1254. Number of Closed Islands
题目 lc1254 · 修改（rev 2） · · 2026-10-25 23:30
body
@@ -1,24 +1,443 @@ +## TL;DR + +- 一座岛是封闭岛，当且仅当它没有一个格子落在网格的边界上（「思路」第 1 小节）。 +- 推荐两遍做法。第一遍从边界上的每块陆地出发，把碰到边界的岛整座淹成水，第二遍像 [[q:lc200]] 那样数剩下的岛（第 2 小节）。 +- 想一遍做完，就在搜一座岛时记下「碰到过边界」，但要把整座岛搜完再下结论。中途停下，没搜到的那半座岛会被当成一座新的封闭岛（第 3 小节）。 +- 这题 0 是陆地、1 是水，和 200 正好相反。 +- 用 BFS 写。递归 DFS 在 100 × 100 的全陆地网格上要套约 1 万层调用，Python 默认只允许 1000 层，实测会抛 `RecursionError`（「代码」第 3 小节）。 +- 时间 O(mn)，空间 O(mn)。 + ## 题目 -网格中 0 是陆地、1 是水，四周都被水包围、不碰到网格边界的岛叫做封闭岛，求封闭岛的数量。 +输入是一个 m 行 n 列的整数网格 `grid`，每个格子是 0 或 1，**0 是陆地，1 是水**。上下左右相邻的陆地格子连在一起算一座岛，斜对角相邻不算相连。一座岛如果上、下、左、右四个方向都被水围住，就叫封闭岛（closed island）。要求返回封闭岛的数量。 + +碰到网格边界的岛一律不算封闭岛，因为边界上的格子至少有一侧朝向网格外面，那一侧没有水。 + +LeetCode 上要实现的函数是 `closedIsland(grid)`，返回一个整数。LeetCode 的数据范围是行数和列数都在 1 到 100 之间（未核实），所以网格最多有 10000 个格子。 + +下面是一个 5 行 6 列的例子。坐标写成 (行, 列)，都从 0 开始数： + +```text +1 1 1 1 1 1 +1 0 0 1 0 0 +1 0 1 1 1 1 +1 1 1 0 1 1 +1 1 1 1 1 1 +``` + +网格里有三座岛。岛 A 是 (1, 1)、(1, 2)、(2, 1) 三格，四周都是 1，是封闭岛。岛 B 是 (1, 4)、(1, 5) 两格，其中 (1, 5) 在最后一列，碰到了右边界，不算。岛 C 是单独的 (3, 3)，四周都是 1，是封闭岛。答案是 2。如果照 200 的做法把所有岛都数上，会得到 3，多出来的就是岛 B。 [LeetCode 原题](https://leetcode.com/problems/number-of-closed-islands/) +### 开口先问清的几件事 + +下面几件事题面里不一定说，写代码之前先和面试官确认： + +- **哪个数是陆地。** 面经里 0 是陆地、1 是水。如果面试官说 1 是陆地，就把代码里判断陆地的 `== 0` 换成 `== 1`，淹掉时写入的 `1` 换成 `0`，其余不变。 +- **斜对角算不算相连。** 通常不算，叫 4 连通（4-connectivity），每个格子只看上下左右四个邻居。如果算，就是 8 连通，两遍搜索的方向都从 4 个改成 8 个，见 Follow-up。 +- **能不能改输入。** 下面的代码把访问过的陆地直接改成 1，省掉一个访问标记数组。不能改的话，开头先复制一份网格，或者另开一个同样大小的布尔数组 `visited`，额外空间都是 O(mn)。 +- **网格会不会是空的。** 按上面的数据范围，网格至少有 1 行 1 列。面试里如果可能为空，开头先判断，空网格直接返回 0。 + +## 面经里怎么考的 + +Glassdoor 上 2026 年 10 月有一篇 Amazon Tel Aviv 的 SDE 电话面试。整场 60 分钟，用 Zoom，先问了两道 Leadership Principles 题（简称 LP，是 Amazon 按自家的领导力准则出的行为面试题），然后在 Amazon 自己的在线编辑器里写代码。帖子没有写题号，只说是 Number of Islands（[[q:lc200]]）的变体：整数网格里 0 是陆地、1 是水，碰到边界的岛不算。这和 1254 的题意一致，所以网站把这次出现记在 1254 名下，可信度记为「推断」。 + +帖子里提到，面试官要求先讲高层的算法，再动手写代码。按这个要求，准备的顺序是： + +1. 先确认题意，也就是上面「开口先问清的几件事」：0 是陆地，只看上下左右，碰边界的岛不算，能不能改输入。 +2. 再讲高层思路。两道 LP 题已经占掉了这 60 分钟里的一部分，思路两三句话讲完就停，留出写代码和手动检查的时间。一座岛封闭等于它不碰边界，所以先从边界出发把碰边的岛淹掉，再数剩下的岛。接着说复杂度 O(mn)，以及为什么用 BFS、不用递归。英文说法见最后一节。 +3. 面试官认可之后再写代码。这个编辑器能不能运行代码事先不知道，按不能运行来准备：写完拿「题目」里的 5 × 6 例子手动走一遍，边走边说第一遍从 (1, 5) 出发淹掉岛 B，第二遍在 (1, 1) 和 (3, 3) 各计一次数。 + ## 思路 -一座岛只要有一个格子在网格边界上，就不是封闭的。和 130 一样反过来做：先从四条边上的所有陆地出发，把和边界连通的陆地全部淹掉（改成 1）。剩下的每座岛都不碰边界，因此都是封闭岛，接下来就是 200 的数岛问题。这样把「判断一座岛是否碰到边界」拆成了两次简单的遍历，比在一次搜索中同时记录是否碰边更不容易出错。 - -## 步骤 - -1. 遍历四条边上的每个格子，值为 0 时从这里搜索，把能到达的 0 全部改成 1。 -2. 扫描整个网格，遇到 0 时计数加 1，并搜索整座岛，把它改成 1。 +### 1. 「封闭」就是「不碰边界」 + +题目用「四周都被水围住」定义封闭，照着这个定义去检查不方便。先把它换成一个好检查的条件：**一座岛是封闭岛，当且仅当它没有一个格子在网格的边界上**（第一行、最后一行、第一列、最后一列）。两个方向分别看。 + +- 岛 I 没有格子在边界上。任取 I 里的一格 X，X 不在边界上，所以它上下左右四个邻居都在网格里。是陆地的邻居和 X 相连，属于岛 I 本身，不属于岛 I 的邻居就只能是水。对 I 的每一格都是这样，所以和 I 相邻、但不属于 I 的格子全是水，I 是封闭岛。 +- 岛 I 有一格 Y 在边界上。Y 至少有一侧是网格外面，那里没有水，所以 I 不是封闭岛。 + +这样问题就变成了「数有多少座岛不碰边界」。 + +### 2. 两遍做法：先把碰边的岛淹掉 + +> [!term] 洪水填充（flood fill） +> 从一个格子出发，把和它连通、取值相同的格子全部找出来，通常顺手改成另一个值。画图软件里的油漆桶就是这个操作。这题里「淹掉一座岛」就是从岛上任意一格做 flood fill，把整座岛的 0 都改成 1。 + +flood fill 可以用 BFS 或 DFS 实现。BFS（breadth-first search，广度优先搜索）用一个队列，先处理离起点一步的格子，再处理两步的，一圈一圈往外扩。DFS（depth-first search，深度优先搜索）沿一条路一直走到走不下去再退回来，通常写成递归：每往前走一格就多调用一层函数，这些还没返回的调用一层压一层，存在调用栈（call stack）里，递归时也常叫递归栈。两种走法最后访问到的格子一样，都是起点所在的整座岛，差别在访问顺序和占用的内存。 + +两遍做法分三步： + +1. 第一遍扫描边界上的每个格子，遇到陆地就从它做 flood fill，把能走到的陆地全部改成 1。 +2. 第二遍扫描整个网格，每遇到一个 0，说明找到一座还没淹的岛，计数加 1，再从它做 flood fill 把整座岛改成 1，后面扫到这些格子就会跳过。这一遍和 [[q:lc200]] 数岛的做法完全一样。 3. 返回计数。 +要说明这个做法是对的，分两种岛来看。 + +- 碰到边界的岛，至少有一格 Y 在边界上。第一遍扫到 Y 时，如果 Y 还是 0，就从 Y 出发做 flood fill，整座岛都被改成 1。如果 Y 已经是 1，说明这座岛在之前从另一个边界格出发的 flood fill 里已经被整座淹掉了。所以第一遍结束时，碰边的岛一格不剩。 +- 不碰边界的岛，第一遍一格都不会动。flood fill 只沿着相连的陆地走，第一遍的起点都在边界上，走到的格子都和某个边界格属于同一座岛。不碰边界的岛和任何边界格都不相连，走不到。 + +所以第一遍之后剩下的岛，恰好是原来不碰边界的那些。按第 1 小节，它们都是封闭岛，第二遍数出来的就是答案。 + +拿「题目」里的例子走一遍。边界上只有 (1, 5) 是 0，第一遍从它出发，淹掉 (1, 5) 和 (1, 4)，也就是岛 B。之后网格变成： + +```text +1 1 1 1 1 1 +1 0 0 1 1 1 +1 0 1 1 1 1 +1 1 1 0 1 1 +1 1 1 1 1 1 +``` + +第二遍按行扫描，先在 (1, 1) 遇到 0，计数变成 1，淹掉岛 A。再在 (3, 3) 遇到 0，计数变成 2，淹掉岛 C。返回 2。 + +这种从边界往里搜的思路，在 [[q:lc130]]（把被围住的 `'O'` 改成 `'X'`）、[[q:lc1020]]（数走不出边界的陆地格子，那题 1 是陆地）和 [[q:lc417]]（从两个大洋往内陆逆流）里也会用到。 + +两遍做法里，每次 flood fill 都把整座岛淹完，中间没有「什么时候可以停」的判断，所以比下面第 3 小节的一遍做法少一个出错的地方。 + +搜索时要在格子入队的那一刻就把它改成 1，和 [[q:lc200]] 的要求一样。如果等出队时才改，一个格子在出队之前可能已经被好几个邻居各放进队列一次，后果取决于出队时有没有检查： + +- 出队时先检查这一格，已经是 1 就跳过。结果仍然对，只是做了重复的工作。实测 100 × 100 的全陆地网格上，入队时标记一共入队 10000 次，这种写法入队 19801 次。 +- 只是把标记改到出队时做，也就是 `popleft()` 之后写 `grid[x][y] = 1`，不加检查。同一格在队列里的每一份重复弹出来时，都会把它还没改成 1 的邻居再放进队列一次，重复的份数一层层累加。在全陆地网格上从 (0, 0) 出发，格子 (i, j) 被放进队列的次数，等于从 (0, 0) 只往下、往右走到 (i, j) 的路径条数，k × k 的网格一共入队 C(2k, k) − 1 次，随边长指数增长。实测 10 × 10 入队 184755 次，12 × 12 入队 2704155 次、用了约 2.6 秒，100 × 100 跑不完。 + +### 3. 一遍做法：边搜边记，搜完再下结论 + +也可以只扫一遍网格。每遇到一块还没访问过的陆地，就把它所在的整座岛搜一遍，搜的同时用变量 `closed` 记录这座岛是不是封闭的。`closed` 一开始是 `True`，搜到任何一个边界格就改成 `False`。整座岛搜完之后，`closed` 还是 `True` 才计数。 + +这里有一个坑。碰到边界格时，很容易想「这座岛已经确定不封闭了，可以直接停」，但停下来会出错。被搜过的格子已经改成了 1，在后面的搜索看来它们和水一样。如果停在半路，这座岛没搜到的那部分还是 0，之后扫描到它时会从它开始一次新的搜索。这部分的四周恰好被刚才改成 1 的格子围住，看起来就像一座不碰边界的封闭岛。 + +碰到边界就停的版本，最小要 3 × 3 的网格才会出错。行数或列数不超过 2 时，每一格都在边界上，每次搜索一开始就会把 `closed` 改成 `False`，答案总是 0，和正确答案一样。下面这个 3 × 3 网格就是一个反例，正确答案是 0： + +```text +1 0 1 +1 0 1 +1 1 1 +``` + +岛只有 (0, 1) 和 (1, 1) 两格，(0, 1) 在第一行，碰到了上边界。碰到边界就停的版本这样走： + +1. 按行扫描，先在 (0, 1) 遇到 0，把它改成 1 并入队。 +2. 弹出 (0, 1)，发现它在边界上，把 `closed` 设成 `False` 并跳出循环。(1, 1) 还没来得及入队，仍然是 0。 +3. 继续扫描，在 (1, 1) 遇到 0，开始一次新的搜索。(1, 1) 不在边界上，它的四个邻居 (0, 1)、(2, 1)、(1, 0)、(1, 2) 现在都是 1，搜索到此结束，`closed` 保持 `True`，计数加 1。 + +最后返回 1，比正确答案多 1。大网格上同样会错，100 × 100 的全陆地网格答案是 0，这个版本实测返回 1。正确的写法是碰到边界只改 `closed`、不跳出循环，见「代码」第 2 小节。 + +递归写法里，同一个错误换了个样子。常见的一遍递归是写一个函数 `closed(r, c)`，返回从 (r, c) 出发的这一块是否不碰边界：走出网格返回 `False`，碰到水返回 `True`，否则把当前格改成 1，再看四个方向。如果把四个方向写成 + +```python +return closed(r + 1, c) and closed(r - 1, c) and closed(r, c + 1) and closed(r, c - 1) +``` + +就会出错。Python 的 `and` 是短路求值（short-circuit evaluation），左边已经是 `False`，右边就不再计算。于是某个方向一旦走出网格，后面几个方向就不搜了，效果和碰到边界就停一样。反例同样是 3 × 3，正确答案是 0： + +```text +1 1 0 +1 0 0 +1 1 1 +``` + +扫描先在 (0, 2) 遇到 0，从它开始递归，先往下到 (1, 2)。(1, 2) 往下是水，返回 `True`。往上是已经改成 1 的 (0, 2)，也返回 `True`。往右走出了网格，返回 `False`，于是往左的 (1, 1) 没有被调用，仍然是 0。之后扫描到 (1, 1) 时，它四周都是 1，被算成一座封闭岛，函数返回 1。改法是先把四个方向的结果分别存进变量，四个方向都搜完再用 `and` 合起来，见「代码」第 3 小节。把 `and` 换成按位与 `&` 也行，`&` 不短路，四个调用都会执行，实测在这个反例上返回 0。 + +两种做法的复杂度相同。面试默认用两遍做法，它没有「什么时候停」的判断，写错的机会少。面试官明确要求只遍历一次网格时，再用一遍做法。 + +## 代码 + +下面四段代码都在 2026-10-25 用 Python 3.12.10 跑过，用例和随机测试的结果见「测试用例」。 + +### 1. 两遍 BFS（推荐） + +```python +from collections import deque + +def closedIsland(grid): + m, n = len(grid), len(grid[0]) + + def sink(r, c): + # 把 (r, c) 所在的整座岛改成水（1）。入队时就标记，避免重复入队 + grid[r][c] = 1 + q = deque([(r, c)]) + while q: + x, y = q.popleft() + for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)): + if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0: + grid[nx][ny] = 1 + q.append((nx, ny)) + + # 第一遍：从边界上的每块陆地出发，淹掉所有碰到边界的岛 + for r in range(m): + for c in range(n): + on_border = r == 0 or r == m - 1 or c == 0 or c == n - 1 + if on_border and grid[r][c] == 0: + sink(r, c) + + # 第二遍：剩下的每座岛都不碰边界，数一座淹一座 + count = 0 + for r in range(m): + for c in range(n): + if grid[r][c] == 0: + count += 1 + sink(r, c) + return count +``` + +第一遍为了写法简单，扫了整个网格、只处理边界格。也可以只遍历四条边，复杂度不变。这个函数会改动传入的 `grid`，面试官不让改输入时，在开头加一行 `grid = [row[:] for row in grid]`。 + +### 2. 一遍 BFS + +```python +from collections import deque + +def closedIsland_onepass(grid): + m, n = len(grid), len(grid[0]) + count = 0 + for r in range(m): + for c in range(n): + if grid[r][c] != 0: + continue + closed = True + grid[r][c] = 1 + q = deque([(r, c)]) + while q: + x, y = q.popleft() + if x == 0 or x == m - 1 or y == 0 or y == n - 1: + closed = False # 记下来，但继续把整座岛搜完 + for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)): + if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0: + grid[nx][ny] = 1 + q.append((nx, ny)) + if closed: + count += 1 + return count +``` + +在 `closed = False` 后面加一行 `break`，就是第 3 小节说的碰到边界就停的错误版本。在 `[[1,0,1],[1,0,1],[1,1,1]]` 上，这一版返回 0，加了 `break` 的版本返回 1。 + +### 3. 递归 DFS，以及 Python 的递归深度 + +先是两遍做法的递归版本。和代码 1 相比，`sink` 改成了递归，判断「是不是陆地」也挪到了 `sink` 的开头： + +```python +def closedIsland_dfs(grid): + m, n = len(grid), len(grid[0]) + + def sink(r, c): + # 走出网格或不是陆地就返回，否则改成 1，再往四个方向递归 + if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != 0: + return + grid[r][c] = 1 + sink(r + 1, c) + sink(r - 1, c) + sink(r, c + 1) + sink(r, c - 1) + + for r in range(m): + for c in range(n): + if r == 0 or r == m - 1 or c == 0 or c == n - 1: + sink(r, c) + count = 0 + for r in range(m): + for c in range(n): + if grid[r][c] == 0: + count += 1 + sink(r, c) + return count +``` + +再是「思路」第 3 小节说的一遍递归版本： + +```python +def closedIsland_dfs_onepass(grid): + m, n = len(grid), len(grid[0]) + + def closed(r, c): + # 返回 (r, c) 所在的这一块是否不碰边界，同时把整块标记成 1 + if r < 0 or r >= m or c < 0 or c >= n: + return False # 走出网格，说明碰到了边界 + if grid[r][c] == 1: + return True + grid[r][c] = 1 + down = closed(r + 1, c) + up = closed(r - 1, c) + right = closed(r, c + 1) + left = closed(r, c - 1) + return down and up and right and left # 四个方向都搜完了再合并 + + count = 0 + for r in range(m): + for c in range(n): + if grid[r][c] == 0 and closed(r, c): + count += 1 + return count +``` + +Python 限制了递归最多能套多少层，`sys.getrecursionlimit()` 默认返回 1000，超过就抛 `RecursionError`。两个递归版本都是每往前走一格陆地就多套一层调用，所以递归深度最多是一座岛的格子数再加 1，多出来的那一层是最后一次探到水或网格外、马上返回的调用。2026-10-25 在 Python 3.12.10（Windows）上实测，两个递归版本的结果相同： + +| 输入 | 递归版本在默认上限 1000 下 | 递归版本实测最大递归深度 | 两遍 BFS | +| --- | --- | --- | --- | +| 100 × 100 全陆地 | 抛 `RecursionError` | 10001 | 返回 0 | +| 100 × 100，外圈一圈水，内部 98 × 98 全陆地 | 抛 `RecursionError` | 9605 | 返回 1 | + +递归深度能达到格子总数，是因为递归会像蛇一样把整张网格串成一条路。以「下、上、右、左」的方向顺序为例，从 (0, 0) 出发会先一路往下走到 (99, 0)，下面没路了就往右到 (99, 1)，再一路往上到 (0, 1)，然后往右到 (0, 2)，再一路往下，就这样来回走完全部 10000 格。每一步都发生在上一步的调用里面，走完之前一层都不返回。用两遍递归版本换成另外三种方向顺序（右左下上、上下左右、右下左上）实测，递归也都一路套过了全部 10000 格陆地。默认上限下，两个递归版本在全陆地的正方形网格上都是从 32 × 32（1024 格）开始出错，31 × 31（961 格）还能跑完。所以在递归上限保持默认 1000 的 Python 里（本地运行，或者没有调过上限的在线编辑器），这题数据范围内的大网格会让递归写法出错。LeetCode 判题环境把上限设成了多少，未核实。 + +有两种改法： + +- 改用 BFS，或者用显式栈（explicit stack）。显式栈就是自己拿一个 Python 列表当栈，用 `append` 和 `pop` 存取待处理的格子，代替递归调用。把代码 1 里的 `deque` 换成列表、`popleft()` 换成 `pop()` 就是这个写法，它在默认上限下跑完了上表两个网格，因为它根本不递归。推荐这个改法。 +- 在开头调高上限，比如 `sys.setrecursionlimit(20000)`。实测 `setrecursionlimit(10050)` 和 `setrecursionlimit(20000)` 都能跑完上表的两个网格，每个约 0.01 秒。300 × 300 的全陆地网格要把上限调到 100000，实测递归一路套过了全部 90000 格，和 [[q:lc200]] 页面说的 9 万层一致，这么深在本机的 Python 3.12.10 上也跑完了，用了约 0.08 秒。别的 Python 版本、LeetCode 的判题环境能承受多深的递归，未核实。面试时说清这个风险，再用 BFS。 + +## 复杂度 + +时间 O(mn)。两遍扫描各看 mn 个格子。每块陆地在整个过程中只会从 0 改成 1 一次，也只会入队一次，出队时看 4 个邻居，所以所有 flood fill 加起来是 O(mn)。 + +空间 O(mn)。代码直接在输入上做标记，没有另开数组，额外的空间是队列。队列里的格子不会超过格子总数，这是 O(mn) 的上界。实测 100 × 100 全陆地网格上队列最长是 100 个格子（BFS 从角上出发，队列里大致是一条斜线上的格子），远小于这个上界。递归 DFS 的递归栈最坏和一座岛的格子数一样多，这个最坏情况实测能达到（上一节的 10001 层）。不能改输入时，复制网格或另开 `visited` 数组，再加 O(mn)。 + ## 易错点 -- 这题 0 是陆地、1 是水，和 200 正好相反，照搬代码会把判断条件写反。 -- 如果选择在一次搜索中顺便判断是否碰到边界，碰到边界时也不能提前返回，必须把整座岛都标记完，否则剩下的格子在后面会被当成一座新岛。 - -## 复杂度 - -时间 O(mn)，每个格子最多被淹一次；空间 O(mn)，最坏情况下队列或递归栈装下所有格子。 +- **把 0 和 1 弄反。** 这题 0 是陆地，[[q:lc200]] 和 [[q:lc1020]] 都是 1 是陆地。把 200 的判断改成整数照搬过来，代码会去数被陆地围住的水。`[[1,1,1],[1,0,1],[1,1,1]]` 答案是 1，写反的版本返回 0。在「测试用例」一节的 3286 组随机网格上，写反的版本错了 1458 组。另外 200 的网格存的是字符 `'1'` 和 `'0'`，这题存的是整数，原样照搬 `== '1'` 永远不成立。见「题目」。 +- **一遍搜索碰到边界就停。** 剩下没搜到的半座岛四周是刚改成 1 的格子，后面会被当成一座新的封闭岛。`[[1,0,1],[1,0,1],[1,1,1]]` 答案是 0，这样写返回 1。见「思路」第 3 小节。 +- **递归里用 `and` 连接四个方向。** `and` 短路，一个方向返回 `False` 后其余方向不再搜，和碰到边界就停是同一个错误。`[[1,1,0],[1,0,0],[1,1,1]]` 答案是 0，这样写返回 1。见「思路」第 3 小节。 +- **出队时才标记。** 出队时检查了「已经是 1 就跳过」，结果仍然对，100 × 100 全陆地网格上入队次数从 10000 涨到 19801。连这个检查也没有，入队次数随边长指数增长，12 × 12 就要入队 270 万次。见「思路」第 2 小节。 +- **递归 DFS 超过递归深度上限。** Python 默认上限是 1000，32 × 32 的全陆地网格就会抛 `RecursionError`。见「代码」第 3 小节。 +- **忘了边界格本身不封闭。** 边界上的陆地格就算在网格里的邻居全是水，也不是封闭岛，比如 `[[0]]` 的答案是 0。行数或列数不超过 2 的网格，每一格都在边界上，答案一定是 0。 + +## 测试用例 + +| 输入 | 期望 | 测的是什么 | +| --- | --- | --- | +| 「题目」里的 5 × 6 例子 | 2 | 基本情况，碰右边界的岛 B 不算 | +| `[[0]]` | 0 | 单格陆地，在边界上 | +| `[[1]]` | 0 | 单格水 | +| `[[0,1,0,0]]` | 0 | 只有 1 行，每格都在边界上 | +| `[[0],[0],[1],[0]]` | 0 | 只有 1 列 | +| `[[1,1,1],[1,0,1],[1,1,1]]` | 1 | 最小的封闭岛，写反 0 和 1 的版本返回 0 | +| `[[1,1,1,1,1],[1,0,1,0,1],[1,1,1,1,1]]` | 2 | 被一格水隔开的两座岛分开数 | +| `[[0,1,1],[1,0,1],[1,1,1]]` | 1 | 斜对角不算相连，(1, 1) 自己是一座封闭岛 | +| `[[1,0,1],[1,0,1],[1,1,1]]` | 0 | 碰到边界就停的反例，错误版本返回 1 | +| `[[1,1,0],[1,0,0],[1,1,1]]` | 0 | `and` 短路的反例，错误版本返回 1 | +| 5 × 5，外圈全是 0，里面一圈 1，正中一个 0 | 1 | 边界全是陆地，外圈那座岛不算，正中那格算 | +| 下面的 6 × 6 蛇形岛 | 0 | 只有尾巴 (5, 1) 碰到下边界，第一遍要沿整条蛇淹完 | +| 同一条蛇，把 (5, 1) 改成 1 | 1 | 同样的形状，不碰边界就算 | +| 100 × 100 全 0 | 0 | 最大的全陆地网格，递归 DFS 在默认上限下出错 | +| 100 × 100 全 1 | 0 | 没有陆地 | +| 100 × 100，外圈是水、内部全陆地 | 1 | 最大的一座封闭岛，有 9604 格，递归 DFS 在默认上限下出错 | + +蛇形岛的网格： + +```text +1 1 1 1 1 1 +1 0 0 0 0 1 +1 1 1 1 0 1 +1 0 0 0 0 1 +1 0 1 1 1 1 +1 0 1 1 1 1 +``` + +2026-10-25 在 Python 3.12.10 上，四个正确版本（两遍 BFS、一遍 BFS、两遍递归 DFS、一遍递归 DFS）都跑了上表每一行，结果都和「期望」一列一致。递归版本跑之前先把上限调到 20000。 + +另外做了对拍。对拍是写一个简单、容易确认没错的暴力参照，在大量随机输入上和正式解法比对输出，有一组不一样就说明其中一个写错了。这里的暴力参照用并查集（union-find，Follow-up 最后一条有介绍）把所有陆地按 4 连通分组，记下每组的全部格子，再逐组检查有没有格子在边界上。它不改输入，也不用「先淹边界」的思路，和正式解法的做法不同。2026-10-25 生成了 3286 组网格： + +- 2 组 1 × 1，全 0 和全 1 各一组。 +- 40 组只有 1 行或 1 列的网格，长度从 1 到 10，有全 0、全 1，也有随机的。 +- 14 组全 0 或全 1，尺寸是 2 × 2、3 × 3、5 × 7、10 × 10、1 × 100、100 × 1、100 × 100。 +- 100 组边界全是陆地、内部随机，100 组边界全是水、内部随机，行列各在 1 到 12 之间。 +- 3000 组随机网格，行列各在 1 到 10 之间，陆地比例从 0.2 到 0.8 不等，也有完全随机的。 +- 30 组随机大网格，行列各在 50 到 100 之间。 + +四个正确版本和代码 1 的显式栈写法，在全部 3286 组上都和暴力参照一致。三个错误版本在同一批网格上分别答错了一部分：碰到边界就停的错了 778 组，`and` 短路的错了 848 组，0 和 1 写反的错了 1458 组。 + +同一天又用第二个参照复查了一遍。它完全不做搜索：先把边界上的陆地标成「通到外面」，再反复把挨着这类格子的陆地也标上，直到没有变化，然后用同样反复取最小编号的办法给剩下的陆地分组。行数、列数都不超过 4 的网格一共 74954 个，全部穷举，四个正确版本和显式栈写法都和它一致。三个错误版本在这批网格里最小的出错网格都是 3 × 3，行数或列数不超过 2 的网格一个也没出错，和「思路」第 3 小节的分析一致。 + +## Follow-up + +- **求所有封闭岛的总面积。** 这就是 [[q:lc1020]]，只是那题 1 是陆地。第一遍不变，第二遍不用再搜，直接数剩下多少个 0，也就是 `sum(row.count(0) for row in grid)`。第 2 小节说明了第一遍之后剩下的每块陆地都属于某座封闭岛，所以剩下的 0 的个数就是封闭岛的总面积。 +- **求最大的封闭岛面积。** 第一遍不变。第二遍里让 `sink` 返回这次淹掉了多少格，每出队一格计一次，对每座岛取最大值。没有封闭岛时返回 0。上面两条和下面的 8 连通，2026-10-25 都和暴力参照对拍了 2000 组随机网格，全部一致。 + +```python +from collections import deque + +def maxClosedIslandArea(grid): + m, n = len(grid), len(grid[0]) + + def sink(r, c): + # 和代码 1 的 sink 一样，只是多数一下这次淹掉了几格 + grid[r][c] = 1 + q = deque([(r, c)]) + size = 0 + while q: + x, y = q.popleft() + size += 1 + for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)): + if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0: + grid[nx][ny] = 1 + q.append((nx, ny)) + return size + + for r in range(m): + for c in range(n): + if (r == 0 or r == m - 1 or c == 0 or c == n - 1) and grid[r][c] == 0: + sink(r, c) + best = 0 + for r in range(m): + for c in range(n): + if grid[r][c] == 0: + best = max(best, sink(r, c)) + return best +``` + +这段代码另外和「测试用例」里的第二个参照比对过 77338 个网格，其中包括行列都不超过 4 的全部 74954 个，全部一致。 + +- **斜对角也算相连，也就是 8 连通。** 两遍搜索的方向都加上四个斜方向。第 1 小节的论证照样成立：不在边界上的格子，8 个邻居都在网格里，不属于这座岛的只能是水。`[[0,1,1],[1,0,1],[1,1,1]]` 在 4 连通下答案是 1，在 8 连通下 (1, 1) 和角上的 (0, 0) 连成一座岛、碰到了边界，答案变成 0。对拍的 2000 组随机网格里，有 626 组两种连通方式的答案不同。 +- **不能修改输入。** 开头复制一份网格，或者另开一个 `visited` 布尔数组，把代码里的「改成 1」换成「标记已访问」，额外空间 O(mn)。 +- **陆地一格一格加进来，每加一格都要当前的封闭岛数量。** 每次都重新跑两遍是 O(mn)，加 k 格就是 O(k × mn)。更快的做法是并查集（union-find）。它维护「哪些格子连在一起」，`find` 找一个格子所在集合的代表，`union` 把两个集合合并，[[q:lc200]] 的 Follow-up 就用它做数岛的在线版本（LC305）。这题再加一个虚拟节点 `BORDER`，代表网格外面：边界上的格子一变成陆地，就和 `BORDER` 合并。这样所有碰边的岛都和 `BORDER` 在同一个集合里，其余每个集合各是一座封闭岛。代码里的 `comps` 只数陆地格子和 `BORDER` 组成的集合，水格子从来不进任何集合，所以封闭岛数量等于 `comps` 减 1（减掉 `BORDER` 所在的那个）。每加一格，集合数先加 1，它在边界上就和 `BORDER` 合并，再和四个邻居里的陆地逐个合并，每成功合并一次集合数减 1。同一格重复加，什么都不变。 + +```python +def closedIslandsOnline(m, n, positions): + BORDER = m * n # 虚拟节点，代表网格外面 + parent = list(range(m * n + 1)) + size = [1] * (m * n + 1) # 每个集合的格子数，只对代表有意义 + + def find(x): + while parent[x] != x: + parent[x] = parent[parent[x]] # 路径减半 + x = parent[x] + return x + + def union(a, b): + ra, rb = find(a), find(b) + if ra == rb: + return False + if size[ra] > size[rb]: # 按大小合并：小集合挂到大集合下面 + ra, rb = rb, ra + parent[ra] = rb + size[rb] += size[ra] + return True + + land = set() + comps = 1 # 集合个数，BORDER 自己先算一个 + res = [] + for r, c in positions: + if (r, c) not in land: + land.add((r, c)) + comps += 1 + idx = r * n + c + if (r == 0 or r == m - 1 or c == 0 or c == n - 1) and union(idx, BORDER): + comps -= 1 + for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)): + if (nr, nc) in land and union(idx, nr * n + nc): + comps -= 1 + res.append(comps - 1) # 去掉 BORDER 所在的那个集合 + return res +``` + +`closedIslandsOnline(3, 3, [(1, 1), (0, 1), (2, 2), (0, 1)])` 实测返回 `[1, 0, 0, 0]`。先加正中的 (1, 1)，它自己是一座封闭岛。再加上边界的 (0, 1)，它和 `BORDER` 合并，又和 (1, 1) 相连，这座岛碰边了，数量变成 0。(2, 2) 在角上，只和 `BORDER` 合并，仍是 0。最后重复加 (0, 1)，不变。2026-10-25 的对拍里，对 3286 组中不超过 100 格的 3239 组网格，把陆地格按随机顺序逐个加入，末尾再重复加两格，每一步的结果都和暴力参照对当时的网格算出的答案一致。 + +代码同时用了两个优化。路径减半（path halving）是查找时顺手让每个节点改指向它的祖父节点，把树压扁，[[q:lc200]] 页面把同一行代码叫作「路径压缩（隔代）」，说的是同一个写法。按大小合并（union by size）是合并时总把格子少的集合挂到格子多的集合下面，避免树越长越高。两个一起用，每次操作的均摊时间接近常数。开头建 `parent` 和 `size` 两个数组要 O(mn)，之后加 k 格总共接近 O(k)，合起来接近 O(mn + k)，比每次重算的 O(k × mn) 快得多。这个做法只能加陆地，不能把陆地变回水：并查集只会合并集合，拆不开，陆地变回水时只能整张网格重算，O(mn)。 + +## 英文讲法 + +> [!say] Before I start, I'd like to confirm a few things. Zero is land and one is water. Cells connect only up, down, left, and right, not diagonally. An island that touches the edge of the grid doesn't count as closed. Is it OK if I mark visited cells by modifying the grid? + +> [!say] Here's the high-level idea before I write any code. An island is closed exactly when none of its cells is on the border, because a border cell always has a side facing outside the grid. So I'll make two passes. In the first pass, I start from every land cell on the border and flood-fill it, turning that whole island into water. After that, every island left is closed, so the second pass is just Number of Islands. I scan the grid, and each time I find land, I count one island and flood-fill it. Does this approach sound good before I start coding? + +> [!say] Every land cell is turned into water once, so the time is O(m times n), and the queue holds at most m times n cells. I'll use BFS with a queue instead of recursive DFS. On a 100 by 100 grid that's all land, the recursion would go about 10,000 calls deep, and Python's default recursion limit is 1,000. + +> [!say] If you'd like a single pass, I'd flood-fill each island once and keep a flag that turns false as soon as I reach a border cell. I still have to finish the whole island before moving on. If I stopped early, the cells I hadn't visited would be counted later as a separate closed island.