更新题目 1254. Number of Closed Islands

题目 lc1254 · 修改（rev 3） · cc · 2026-10-25 23:32
body

@@ -211,5 +211,5 @@
 ```
 
-在 `closed = False` 后面加一行 `break`，就是第 3 小节说的碰到边界就停的错误版本。在 `[[1,0,1],[1,0,1],[1,1,1]]` 上，这一版返回 0，加了 `break` 的版本返回 1。
+在 `closed = False` 后面加一行 `break`，就是「思路」第 3 小节说的碰到边界就停的错误版本。在 `[[1,0,1],[1,0,1],[1,1,1]]` 上，这一版返回 0，加了 `break` 的版本返回 1。
 
 ### 3. 递归 DFS，以及 Python 的递归深度
@@ -349,5 +349,5 @@
 ## Follow-up
 
-- **求所有封闭岛的总面积。** 这就是 [[q:lc1020]]，只是那题 1 是陆地。第一遍不变，第二遍不用再搜，直接数剩下多少个 0，也就是 `sum(row.count(0) for row in grid)`。第 2 小节说明了第一遍之后剩下的每块陆地都属于某座封闭岛，所以剩下的 0 的个数就是封闭岛的总面积。
+- **求所有封闭岛的总面积。** 这就是 [[q:lc1020]]，只是那题 1 是陆地。第一遍不变，第二遍不用再搜，直接数剩下多少个 0，也就是 `sum(row.count(0) for row in grid)`。「思路」第 2 小节说明了第一遍之后剩下的每块陆地都属于某座封闭岛，所以剩下的 0 的个数就是封闭岛的总面积。
 - **求最大的封闭岛面积。** 第一遍不变。第二遍里让 `sink` 返回这次淹掉了多少格，每出队一格计一次，对每座岛取最大值。没有封闭岛时返回 0。上面两条和下面的 8 连通，2026-10-25 都和暴力参照对拍了 2000 组随机网格，全部一致。
 
@@ -386,5 +386,5 @@
 这段代码另外和「测试用例」里的第二个参照比对过 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 组两种连通方式的答案不同。
+- **斜对角也算相连，也就是 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。同一格重复加，什么都不变。