岛屿数量
一块块地把岛沉掉，数一共沉了几座
网格里 '1' 是陆地、'0' 是水；只有上下左右相邻的陆地才连通（对角线不算）。一座「岛」就是一块四向连通的陆地—— 我们要数的是连通块的个数，不是 '1' 的总数。主循环逐格扫描找到新岛入口， DFS/BFS 负责把整座岛沉掉，避免重复计数。
边界测试 · 切换后整段动画会重算
输入地图：1 是陆地，0 是水
网格里 '1' 是陆地，'0' 是水。只有上下左右四个方向相邻的陆地才算连在一起，对角线不算。一座「岛」就是一块四向连通的陆地。我们要数的是岛（连通块）的数量。
核心逻辑 · 怎么数岛
- 1.主循环 (r,c) 逐格扫描，只为找到一座新岛的入口。
- 2.遇到未访问的 '1' → count++（发现一座岛）。
- 3.DFS/BFS 从入口出发，把上下左右连通的 '1' 全部沉没（标记已访问）。
- 4.沉没后这些格子不会再触发 count++，避免重复计数。
只看上下左右四个方向，对角线不算连通。
图例
- 未访问陆地 '1'
- 水 '0'
- 正在沉没（栈顶）
- 在调用栈中
- 已沉没（变灰）
- 金框 = 这座岛的入口
- 青框 = 扫描指针
网格地图 · 沉岛过程
读题行优先扫描
关键：先看清地图：哪些是陆地、谁和谁相邻。
不变量：相邻 = 共享一条边（上下左右），不是共享一个角。
代码 · 当前高亮行随帧切换
1func numIslands(grid [][]byte) int {2 m, n := len(grid), len(grid[0])3 count := 04 for r := 0; r < m; r++ {5 for c := 0; c < n; c++ {6 if grid[r][c] == '1' { // 未访问的陆地7 count++ // 发现一座新岛8 dfs(grid, r, c) // 把整座岛沉掉9 }10 }11 }12 return count13}1415func dfs(grid [][]byte, r, c int) {16 if r < 0 || r >= len(grid) ||17 c < 0 || c >= len(grid[0]) ||18 grid[r][c] != '1' { // 越界 / 水 / 已访问19 return20 }21 grid[r][c] = '0' // 沉没：标记为已访问22 dfs(grid, r-1, c) // 上23 dfs(grid, r+1, c) // 下24 dfs(grid, r, c-1) // 左25 dfs(grid, r, c+1) // 右26}
不变量 · 算法为什么对
- · 岛 = 上下左右四向连通的一块陆地（对角不算）；答案数的是连通块个数。
- · 主循环只负责发现新岛入口；count 仅在入口 +1，所以 count == 岛屿数。
- · DFS 沉没（标记已访问）后，该格不再触发 count++，杜绝重复计数与死循环。
- · 递归栈深 = 当前 DFS 路径长度，最坏 O(m·n)；原地改 grid 不等于 O(1) 空间。
时间线 · 点击跳转
主循环看每个格子一次；DFS 只会沉没值为 '1' 的格子，每格最多被沉一次。两者都和格子总数成正比，所以是 m·n 的线性时间。
递归 DFS 的空间来自调用栈，栈深 = 当前 DFS 路径的长度。最坏情况是一条贯穿全图的蛇形岛，路径长达 m·n，递归栈就有 m·n 层。原地把 '1' 改成 '0' 只是省掉了额外的 visited 数组，并不会消除递归栈——所以整体不是 O(1)。
换成 BFS 队列或显式栈做迭代，最坏空间同样是 O(m·n) 量级，但不占用系统递归栈，能避免极端大岛把调用栈压爆。
我会双重循环扫描每个格子。遇到未访问的 '1'，说明发现一座新岛，答案加一。然后用 DFS/BFS 把这个岛上下左右连通的所有 '1' 标记为已访问，避免后续重复计数。每个格子最多处理常数次，所以时间复杂度是 O(m*n)。如果递归 DFS，最坏空间是 O(m*n)。
- 误区 1 · 对角线也算连通
只看上下左右四个方向。对角相邻的两个 '1' 属于两座不同的岛——切到「对角陷阱」用例，5 个 1 就是 5 座岛。
- 误区 2 · 数的是 '1' 的个数
答案是连通块的个数，不是 '1' 的总数。一座岛可能由很多个 '1' 拼成；它们整体只算 1。
- 误区 3 · 不标记已访问
沉没（标记已访问）后才不会被再次进入。否则同一座岛会被反复 count++，DFS 还会在相邻两格之间来回无限递归直到爆栈。
- 误区 4 · 原地改 grid 就是 O(1) 空间
把 '1' 改成 '0' 省掉的只是 visited 数组。递归调用栈最坏仍是 O(m·n)，整体空间并不是 O(1)。
- 误区 5 · 默认递归一定安全
极端大岛上递归 DFS 栈深可达 m·n，可能爆栈。面试时可以补一句：改用 BFS 队列或显式栈做迭代更稳。
迁移练习 · 同一套四向 flood
- →LC695 岛屿的最大面积 — DFS 返回连通块大小，取最大
- →LC130 被围绕的区域 — 从边界反向 flood，剩下的才被围
- →LC417 太平洋大西洋水流 — 两次边界 flood 求交集
- →LC733 图像渲染 / Flood Fill — 同一套四向扩散染色
- →LC547 省份数量 — 邻接矩阵上的连通块，常配 Union-Find