岛屿数量

地图：绿色是陆地，蓝色是水。肉眼看：左上角连成一片是一座岛，右下角单独一格是另一座。

从左到右、从上到下扫网格。每碰到一个还没访问过的陆地，岛屿数就 +1，然后用 DFS 把和它相连的陆地全部标记为已访问，这样同一座岛就不会被重复数。

扫描 (0,0)：扫到 (0,0) 是陆地，而且没访问过。按代码的顺序：先对它 DFS，把整座岛淹掉，等 DFS 结束再给岛屿数 +1。

DFS · 访问 (0,0)：把 (0,0) 标记为已访问（变灰）。然后检查它的上下左右，看哪些也是陆地。

DFS · 右边 (0,1)：(0,0) 右边的 (0,1) 是陆地，走过去，继续对它做 DFS。

DFS · 访问 (0,1)：标记 (0,1)。它右边是水、下边是水，没有新陆地可走，退回 (0,0) 继续看其它方向。

DFS · 下边 (1,0)：(0,0) 下边的 (1,0) 也是陆地，走过去。

DFS · 访问 (1,0)：标记 (1,0)。它周围也没有新陆地了。这座岛的 3 格全部访问完，DFS 结束。

关键帧 · 一次 DFS 淹掉整座岛，count 才 +1：这是这道题的灵魂。刚才一次 DFS 从 (0,0) 出发，把和它连通的 3 格陆地全部淹成已访问，整座岛一次性沉没。DFS 返回后，岛屿数才 +1。所以记住：count 不是每遇到一格陆地就加，而是「外层扫描每启动一次新的 DFS」才加一次——一次 DFS = 一座岛 = 加一。淹岛的作用，就是保证同一座岛不会被重复数。

继续扫描 · 全是水：接着扫 (0,2)、(1,1)、(1,2)、(2,0)、(2,1)——它们要么是水、要么已访问，全部跳过。

扫到 (2,2)：扫到 (2,2) 是陆地，又没访问过。同样：先对它 DFS。

DFS · 访问 (2,2) · count+1：标记 (2,2)。上边是水、左边是水、右和下都越界，是孤零零一座岛，DFS 立刻结束。岛屿数 +1 = 2。

扫描结束：整个网格扫完，一共触发了 2 次「发现新岛」，答案就是 2。

DFS 沿着一个方向一直深入，直到走不动（碰到水或边界）才回头换方向。把一座岛「淹没」靠的就是它。

岛屿最大面积、被围绕的区域、单词搜索……所有「网格里找连通区域」的题，都是这套网格 DFS/BFS。

边界三连：岛屿数量 的边界先看最小规模、特殊输入和最容易触发分支的样例。

① DFS 还是 BFS？——都行：DFS 用递归/栈一条路走到黑，BFS 用队列一圈圈扩散，复杂度一样。② 能不开 visited 吗？——能，直接把走过的陆地改成水 0 原地标记，省空间。③ 空间为什么 O(m×n)？——最坏整张图都是陆地，递归栈 / 队列会压满。

「碰到没访问的就 DFS 染整片」是所有网格连通块题的骨架：LC695 岛屿最大面积（dfs 返回格子数）、LC994 腐烂橘子（改 BFS 多源扩散）、LC130 被围绕的区域——只换「DFS 里做什么」。更多在 图 / 搜索专题 继续。

面试追问：岛屿数量 的追问重点，是把动画里的状态定义、边界和复杂度讲成自己的话。