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

这是一道非常经典的深度优先搜索（DFS）和广度优先搜索（BFS）的应用题，也是理解「网格类 DFS」的绝佳起点。

1. 题目描述

题目链接：LeetCode 200 - Number of Islands

难度：中等

题目描述：

给你一个由 '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

解释：图中所有的 '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')，我们就发现了一个新的岛屿。但是，和这块陆地相邻的所有陆地都属于同一个岛屿，我们不能重复计数。
• 所以，当我们发现一块新的陆地时，我们需要做两件事：
  1. 岛屿数量加 1。
  2. 通过搜索（DFS/BFS）将属于这个岛屿的所有陆地标记为“已访问”，这样在后续的遍历中就不会再重复计算它们。

第三步：关键的「标记」策略

如何标记「已访问」的陆地呢？有两种常见方法：

1. 使用一个额外的二维 visited 数组，记录每个位置是否被访问过。
2. 直接修改原网格：将访问过的陆地 '1' 修改成另一个字符，例如 '0' 或 '2'。这种方法更节省空间，我们通常采用这种方法。

核心算法（洪水填充法）：

1. 初始化岛屿计数器 count = 0。
2. 遍历网格中的每一个单元格 (i, j)。
3. 如果当前单元格是 '1'（未访问的陆地）：
   • 将 count 加 1。
   • 从 (i, j) 开始，进行 DFS 或 BFS，将所有与之相连的陆地（即整个岛屿）全部标记为已访问（例如，改为 '0'）。
4. 遍历完成后，count 就是岛屿的数量。

3. 解决方案详解：深度优先搜索 (DFS)

DFS 的思路是“不撞南墙不回头”。从一块陆地出发，尽可能深地搜索它的四个方向，直到所有相连的陆地都被访问。

步骤拆解：

1. 主函数 numIslands:

   • 处理特殊情况（网格为空）。
   • 遍历每一个格子。
   • 遇到 '1'，就启动一次 DFS，同时计数器加一。

2. DFS 辅助函数 dfs:

   • 递归终止条件：
     • 当前坐标 (i, j) 超出网格边界（i < 0 或 j < 0 或 i >= 行数 或 j >= 列数）。
     • 当前格子不是陆地（是 '0'，也就是海洋或者已访问过的陆地）。
   • 处理当前节点：将当前陆地 '1' 标记为 '0'（表示已访问，防止重复计算）。
   • 递归访问四个方向：对上、下、左、右四个方向的格子调用 DFS 函数。

代码实现（Python）

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # 如果网格是空的，直接返回0
        if not grid or not grid[0]:
            return 0
        
        # 获取网格的行数和列数
        rows, cols = len(grid), len(grid[0])
        count = 0  # 初始化岛屿计数器
        
        # 定义DFS递归函数
        def dfs(i, j):
            # 递归终止条件：越界或者当前格子不是未访问的陆地
            if i < 0 or j < 0 or i >= rows or j >= cols or 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)  # 右
        
        # 遍历网格中的每一个格子
        for i in range(rows):
            for j in range(cols):
                # 如果发现一块未访问的陆地
                if grid[i][j] == '1':
                    count += 1  # 发现一个新岛屿
                    dfs(i, j)   # 用DFS"沉没"整个岛屿，避免重复计算
                    
        return count

DFS 过程图解（以示例1为例）：

1. 遍历到 (0,0)，发现 '1'，count 变为 1。
2. 从 (0,0) 开始 DFS：
   • 标记 (0,0) 为 '0'。
   • 检查上方：越界，返回。
   • 检查下方 (1,0)：是 '1'，递归。
     • 标记 (1,0) 为 '0'。
     • 检查 (1,0) 的四个方向...（这个过程会像洪水一样蔓延，把所有连通的 '1' 都标记为 '0'）。
3. 当这次 DFS 结束时，整个最初的岛屿的所有陆地都被「沉没」了（标记为 '0'）。
4. 继续遍历网格，剩下的格子都是 '0'，所以不会再启动 DFS。
5. 最终 count = 1。

4. 解决方案详解：广度优先搜索 (BFS)

BFS 的思路是“一圈一圈地扩散”。从一块陆地出发，先访问它所有直接相邻的陆地，再访问相邻陆地的相邻陆地。

步骤拆解：

1. 主函数逻辑不变。
2. BFS 辅助过程:
   • 使用一个队列（例如 collections.deque）来存储待访问的陆地坐标。
   • 将起始陆地 (i, j) 加入队列，并立即标记为已访问。
   • 当队列不为空时：
     • 从队列中取出一个坐标 (x, y)。
     • 检查它的四个方向。
     • 如果某个方向 (nx, ny) 是未访问的陆地 '1'，则将其标记为已访问，并加入队列。

代码实现（Python）

from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        count = 0
        
        # 定义四个方向向量：上、右、下、左
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    count += 1
                    # 开始BFS
                    queue = deque([(i, j)])
                    grid[i][j] = '0'  # 标记为已访问
                    
                    while queue:
                        x, y = queue.popleft()
                        # 遍历四个邻居
                        for dx, dy in directions:
                            nx, ny = x + dx, y + dy
                            # 检查新坐标是否合法且是未访问的陆地
                            if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == '1':
                                grid[nx][ny] = '0'  # 标记为已访问
                                queue.append((nx, ny))
        return count

5. 总结与对比

对于本题，DFS 通常更常用，因为代码更简洁。但两者的时间复杂度和空间复杂度都是 O(M × N)，其中 M 和 N 是网格的行数和列数，因为每个点最多被访问一次。

6. 关键点回顾

1. 核心思想：找到一块新陆地 -> 岛屿数+1 -> 标记整个连通分量。
2. 标记已访问：通过修改原数组，将 '1' 变为 '0'，避免重复计算。
3. 搜索方式：DFS（递归/栈）或 BFS（队列）均可。
4. 方向处理：通常使用方向数组 [(-1,0), (1,0), (0,-1), (0,1)] 来简化代码。

这道题是图论搜索的基础，掌握了它，对于后续的「岛屿的最大面积」、「被围绕的区域」等题目都会有很大的帮助。希望这个循序渐进的讲解能让你彻底理解！