03、岛屿数量

今天来说一个经典题目

https://leetcode.cn/problems/number-of-islands/

题目描述

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

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

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

示例 1:

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

示例 2:

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

约束条件:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 '0' 或 '1'

题目题意，一目了然，就是看图里面的区域，我们继续来看一下

什么是岛屿？

岛屿定义：
- 由相邻的陆地 '1' 连接而成
- 相邻：水平或竖直方向（上下左右）
- 不包括对角线方向
- 被水 '0' 包围

示例：
1 1 0 0
1 0 0 1
0 0 1 1

岛屿1: 左上角的三个 '1'
  1 1
  1

岛屿2: 右下角的三个 '1'
      1
    1 1

共 2 个岛屿

核心思想

1. 遍历整个网格
2. 遇到 '1'（陆地）时：
   - 岛屿计数 +1
   - 将整个岛屿"遍历"（标记为已访问）
3. 继续遍历，跳过已访问的格子

问题分析

难点1: 如何识别一个完整的岛屿？
解决: 从一个陆地出发，通过 DFS/BFS 找到所有相邻陆地

难点2: 如何避免重复计数？
解决: 访问过的陆地标记为 '0' 或用 visited 数组

难点3: 如何处理边界？
解决: 递归/循环时检查边界条件

DFS

核心思想

DFS 感染策略：

1. 主循环遍历每个格子
2. 遇到陆地 '1'：
   - 岛屿数 +1
   - 调用 DFS 感染整个岛屿
3. DFS 过程：
   - 将当前格子标记为 '0'（淹没）
   - 向上下左右四个方向递归
   - 遇到边界或水就停止

感染过程就像"洪水淹没"：
从一个点开始，淹没所有相连的陆地

图解分析

以示例 1 为例：

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

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

步骤1: 遍历到 (0,0)，发现陆地 '1'
岛屿数 = 1

开始 DFS 感染：
(0,0) → 标记为 '0'
  ↓ 向下
(1,0) → 标记为 '0'
  ↓ 向右
(1,1) → 标记为 '0'
  ↓ 向上
(0,1) → 标记为 '0'
  ↓ 向右
(0,2) → 标记为 '0'
  ↓ 向右
(0,3) → 标记为 '0'
  ↓ 向下
(1,3) → 标记为 '0'

感染后的网格：
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 感染：
(2,2) → 标记为 '0'

感染后的网格：
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,3) → 标记为 '0'
  ↓ 向右
(3,4) → 标记为 '0'

感染后的网格：
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

最终答案: 3 个岛屿

代码实现

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) {
            return 0;
        }

        int m = grid.size();
        int n = grid[0].size();
        int count = 0;

        // 遍历每个格子
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;           // 发现新岛屿
                    dfs(grid, i, j);   // 淹没整个岛屿
                }
            }
        }

        return count;
    }

private:
    void dfs(vector<vector<char>>& grid, int i, int j) {
        int m = grid.size();
        int n = grid[0].size();

        // 边界检查 + 水域检查
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
            return;
        }

        // 标记为已访问（淹没）
        grid[i][j] = '0';

        // 向四个方向扩散
        dfs(grid, i - 1, j);  // 上
        dfs(grid, i + 1, j);  // 下
        dfs(grid, i, j - 1);  // 左
        dfs(grid, i, j + 1);  // 右
    }
};

时间复杂度: O(m × n) - 每个格子访问一次

空间复杂度: O(m × n) - 递归栈最坏情况（整个网格都是陆地）

[["X","X","X","X"],
 ["X","O","O","X"],
 ["X","X","O","X"],
 ["X","O","X","X"]]