题目描述
思路解析
一句话答案：LeetCode 200 岛屿数量的经典解法是扫描加 DFS 沉岛：逐格扫描网格，每遇到一块还没处理过的陆地就把岛屿数加一，随即用深度优先搜索把与它四连通的整片陆地全改成海水，保证同一座岛只被数一次。时间 O(R×C)，每个格子至多访问一次，空间最坏 O(R×C)。
岛屿数量这道题在问什么
网格里每个格子要么是陆地字符 '1'，要么是海水字符 '0'。水平或竖直方向相邻的陆地连成一座岛，问一共有几座。用图论的话说，这是在数「陆地的连通分量个数」——彼此能通过上下左右走到的陆地算同一块。注意连通只认四个方向，斜对角挨着的两块陆地不算同一座岛，这个定义直接决定后面搜索时只往四个方向扩散。
为什么数岛屿要靠 DFS 洪水填充
逐格扫描很容易发现陆地，难的是别把同一座岛数成好几座——一座大岛横跨几十个格子，扫描时会撞上它几十次。关键观察由此而来：计数的单位是「岛」而不是「格」，所以第一次撞见某座岛时就该把它整个处理掉，让后续扫描再也撞不上它。
怎么「整个处理掉」？从这块陆地出发，向四个方向递归扩散，把所有连得上的陆地统统标记，这个过程像洪水从一点漫开淹没整片区域，所以也叫洪水填充（flood fill），用 DFS 或 BFS 实现都行。参考代码用 DFS 直接把走到的陆地改写成 '0'，形象地说就是把这座岛「沉」进海里。
沉岛操作维护着什么不变量
把数过的岛立刻沉掉，维护的是这样一条不变量：扫描指针之前经过的区域里，不存在任何还没计数的陆地。于是推论非常干净——扫描途中每撞见一个 '1'，它必然属于一座全新的、没数过的岛，放心加一，绝不会重复。
正确性的另一半是「不漏」：DFS 从起点扩散，恰好覆盖与起点连通的所有陆地，既不会漏掉本岛的格子（每个方向都探），也不会淹到别的岛（中间隔着海水，递归在 '0' 处止步）。一次沉岛动作与一座岛严格一一对应，计数自然准确。
递归的边界条件为什么这样写
dfs(i, j) 开头先做两个判断：下标越界直接返回；格子不是 '1'（是海水或已被沉掉）也直接返回。顺序不能反——必须先判越界再取值，否则会数组越界，在 Python 里负下标还会静悄悄绕到另一头，制造更隐蔽的错。过了这两关才把当前格改成 '0'，然后向四个方向递归。把「已访问」和「海水」统一表示成 '0'，让终止条件只剩一条，是这份代码简洁的来源。
复杂度分析与常见追问
时间 O(R×C)：每个格子至多被外层扫描看一次、被 DFS 进入一次，进入后就变 '0' 不会再进。空间 O(R×C)：最坏整张网格全是陆地，递归深度可达格子总数；担心递归栈溢出可以换成显式队列的 BFS，逻辑不变。
两个常见追问：不想破坏输入网格，就另开一个同尺寸的 visited 布尔数组，判断条件改成「是 '1' 且没访问过」，代价是 O(R×C) 额外空间；若进一步问最大岛屿面积（LeetCode 695），让 dfs 返回它沉掉的格子数，外层取最大值即可。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
核心思路 · 扫描 + 沉岛：绿色格子是陆地、蓝色是海水。核心套路就一句：一行一行扫，每碰到一块没访问过的陆地就计数 +1，然后立刻用 DFS 把整座岛沉掉（标记已访问），免得重复数。下面在这张图上一步步演。
准备 · 全图待扫：右边面板上半是岛屿计数器（现在 0），下半是一只 DFS 栈（现在空）。扫描指针停在左上角第一格，准备像读书一样从左到右、从上到下一格一格走。盯住计数器和栈，整道题就是它俩配合。
发现第 1 座岛 · 起点 (0,0)：扫描指针走到 (0,0)，这是一块还没访问过的陆地 → 发现一座新岛屿！计数器 +1 变成 1，把这格压入 DFS 栈，准备把整座岛沉掉。
沉没 (0,0)：取出栈顶 (0,0) 标记为已沉没（变灰），看它上下左右：(1,0)、(0,1) 是相连的新陆地，压入栈待会儿继续沉。
沉没 (0,1)：取出栈顶 (0,1) 标记为已沉没（变灰），看它上下左右：(1,1) 是相连的新陆地，压入栈待会儿继续沉。
沉没 (1,1)：取出栈顶 (1,1) 标记为已沉没（变灰），看它上下左右：都是海水或已访问，这一支到底了。
沉没 (1,0)：取出栈顶 (1,0) 标记为已沉没（变灰），看它上下左右：都是海水或已访问，这一支到底了。 栈空了，这座岛整块沉完。
发现第 2 座岛 · 起点 (0,4)：扫描指针走到 (0,4)，这是一块还没访问过的陆地 → 发现一座新岛屿！计数器 +1 变成 2，把这格压入 DFS 栈，准备把整座岛沉掉。
沉没 (0,4)：取出栈顶 (0,4) 标记为已沉没（变灰），看它上下左右：(0,5) 是相连的新陆地，压入栈待会儿继续沉。
沉没 (0,5)：取出栈顶 (0,5) 标记为已沉没（变灰），看它上下左右：(1,5) 是相连的新陆地，压入栈待会儿继续沉。
沉没 (1,5)：取出栈顶 (1,5) 标记为已沉没（变灰），看它上下左右：都是海水或已访问，这一支到底了。 栈空了，这座岛整块沉完。
发现第 3 座岛 · 起点 (2,3)：扫描指针走到 (2,3)，这是一块还没访问过的陆地 → 发现一座新岛屿！计数器 +1 变成 3，把这格压入 DFS 栈，准备把整座岛沉掉。
沉没 (2,3)：取出栈顶 (2,3) 标记为已沉没（变灰），看它上下左右：(3,3)、(2,4) 是相连的新陆地，压入栈待会儿继续沉。
沉没 (2,4)：取出栈顶 (2,4) 标记为已沉没（变灰），看它上下左右：都是海水或已访问，这一支到底了。
沉没 (3,3)：取出栈顶 (3,3) 标记为已沉没（变灰），看它上下左右：(3,2) 是相连的新陆地，压入栈待会儿继续沉。
沉没 (3,2)：取出栈顶 (3,2) 标记为已沉没（变灰），看它上下左右：(3,1) 是相连的新陆地，压入栈待会儿继续沉。
沉没 (3,1)：取出栈顶 (3,1) 标记为已沉没（变灰），看它上下左右：(4,1) 是相连的新陆地，压入栈待会儿继续沉。
沉没 (4,1)：取出栈顶 (4,1) 标记为已沉没（变灰），看它上下左右：都是海水或已访问，这一支到底了。 栈空了，这座岛整块沉完。
发现第 4 座岛 · 起点 (3,6)：扫描指针走到 (3,6)，这是一块还没访问过的陆地 → 发现一座新岛屿！计数器 +1 变成 4，把这格压入 DFS 栈，准备把整座岛沉掉。
沉没 (3,6)：取出栈顶 (3,6) 标记为已沉没（变灰），看它上下左右：(4,6) 是相连的新陆地，压入栈待会儿继续沉。
沉没 (4,6)：取出栈顶 (4,6) 标记为已沉没（变灰），看它上下左右：都是海水或已访问，这一支到底了。 栈空了，这座岛整块沉完。
扫描结束：整张网格扫完，每座岛都在发现的瞬间被计数、并被 DFS 整块沉没，所以绝不会重复数。最终岛屿总数 = 4。
边界先想清：空海水返回 0；整片陆地连通只算 1 座；最小的一格陆地也是一座岛。
三个高频追问：DFS↔BFS 互换、用 visited 不改原图、以及把「计数」改成「求面积」的变体。
参考代码
def numIslands(grid): if not grid: return 0 R, C = len(grid), len(grid[0]) def dfs(i, j): if i < 0 or j < 0 or i >= R or j >= C: return if grid[i][j] != '1': return # 海水/已沉没 grid[i][j] = '0' # 沉掉这格 dfs(i-1, j); dfs(i+1, j) dfs(i, j-1); dfs(i, j+1) # 四个方向 cnt = 0 for i in range(R): for j in range(C): if grid[i][j] == '1': # 遇到新陆地 cnt += 1 dfs(i, j) # 沉掉整座岛 return cnt复杂度
- 时间：O(R×C)，每个格子最多被访问一次（扫描一次 + DFS 进一次）
- 空间：O(R×C)，最坏全是陆地时，递归栈深度可达格子总数
易错点
面试追问把动画讲成自己的话
追问能不能用 BFS 代替 DFS？
追问不想修改输入网格怎么办？
追问如果还要求最大岛屿面积呢？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
克隆图
LeetCode 133 · 中等 · 沿着 图 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题