好的，我们这次来详细讲解 LeetCode 第 200 题「岛屿数量」。

1. 题目描述

给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

2. 题意理解

我们可以把网格看作一张地图：

• '1' 表示陆地
• '0' 表示海洋
• 相邻的陆地（上下左右相邻）组成一个岛屿
• 目标：统计岛屿的个数

关键点：
如果两个 '1' 在水平或垂直方向相邻，它们属于同一个岛屿。
我们需要找出所有连通的 '1' 的区域数量。

3. 思路分析

这个问题本质上是求无向图中连通分量的个数。
每个格子是一个节点，相邻的陆地之间有边。

常用方法：

1. 深度优先搜索 (DFS)
   从某个 '1' 出发，把所有与之相连的 '1' 标记为已访问（或直接改成 '0'），这样一座岛屿就全部被“淹没”，计数 +1。
2. 广度优先搜索 (BFS)
   类似 DFS，但是用队列实现，从起点向外扩散标记。
3. 并查集 (Union-Find)
   初始化每个 '1' 的父节点为自己，遍历网格，合并相邻的 '1'，最后统计根节点数量。

这里我们用最容易理解的 DFS 来讲解。

4. 算法步骤（DFS 法）

1. 遍历网格的每个单元格 (i, j)。
2. 如果当前单元格是 '1'（陆地）：
   • 岛屿数量 count++
   • 从这个单元格开始进行 DFS，把所有与它相连的陆地标记为已访问（改成 '0'）
3. 继续遍历，跳过已经访问过的（即 '0'）。
4. 返回 count。

DFS 递归过程（以 (i, j) 为起点）：

• 如果 i 或 j 越界，或当前格子是 '0'，则返回。
• 否则，将当前格子标记为 '0'（已访问）。
• 递归访问上下左右四个方向的格子。

5. 详细示例推导

以示例 2 为例：

初始网格：
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

步骤 1：(0,0) 是 '1'，发现新岛屿，计数 = 1，DFS 淹没相连的陆地：

• 从 (0,0) 开始，标记为 '0'，递归到 (0,1)、(1,0) 等，最终将左上角 2x2 的 '1' 全部淹没。

此时网格：

0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 1 1

步骤 2：继续遍历，(2,2) 是 '1'，计数 = 2，DFS 淹没它（它独立，周围没有相邻的 '1'）：

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 1

步骤 3：继续遍历，(3,3) 是 '1'，计数 = 3，DFS 淹没它和 (3,4)：

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

结束，岛屿数量 = 3。

6. 代码实现（DFS）

def numIslands(grid):
    if not grid or not grid[0]:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def dfs(i, j):
        # 越界或不是陆地，返回
        if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] == '0':
            return
        # 标记为已访问
        grid[i][j] = '0'
        # 四个方向递归
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
    
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)
    
    return count

7. 复杂度分析

• 时间复杂度：O(m × n)
  每个格子最多被访问一次（DFS 中不会重复访问已标记为 '0' 的格子）。
• 空间复杂度：O(m × n)
  最坏情况下，整个网格都是陆地，DFS 递归深度可能达到 m × n（不过实际递归栈深度是 O(max(m, n)) 吗？这里注意：递归深度是沿着某条路径，最坏是 O(m+n)，但多个 DFS 调用栈不会同时存在，所以应该是 O(min(m, n))？其实准确说是 O(m × n) 指递归栈空间最坏情况，但通常说 O(m+n) 是递归深度，这里严谨说：递归栈空间 O(m × n) 在全是陆地时可能发生，但一般说 O(min(m, n)) 是错的，应该是 O(max(m, n)) 作为递归深度。我们保守取 O(m × n) 包括整个网格递归的情况，但实际递归深度是 O(m+n)，所以空间复杂度 O(m+n) 更准确。）

实际上，递归深度是网格对角线长度 O(max(m, n))，所以空间复杂度 O(max(m, n))。

8. 变种与扩展

• 如果要统计每个岛屿的面积？
  在 DFS 中返回当前岛屿的格子数即可。
• 如果允许斜对角线相邻也算同一个岛屿？
  DFS/BFS 时遍历 8 个方向而不是 4 个方向。
• 最大岛屿面积？
  对每个岛屿计算大小，取最大值。

这样，我们从问题理解、思路分析、步骤推导到代码实现，完整地讲解了「岛屿数量」这道题。希望你能透彻理解 DFS 在图遍历中的应用！