🔗 岛屿数量

题目来源：200. 岛屿数量 – 力扣（LeetCode）

---

📌 题目描述

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

• 岛屿是由水平或竖直方向上相邻的陆地（'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

解释：存在三个互不相连的陆地区域。

---

⚠️ 提示

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

---

💡 解法：深度优先搜索（DFS）—— O(mn) 时间，O(mn) 空间（最坏）

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        // 遍历整个网格
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                // 发现陆地，说明找到一个新岛屿
                if (grid[i][j] == '1') {
                    count++;
                    // 用 DFS 将该岛屿所有陆地“淹没”（标记为 '0'）
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int i, int j) {
        // 边界检查 + 水域/已访问检查
        if (i < 0 || i >= grid.length || 
            j < 0 || j >= grid[0].length || 
            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); // 左
    }
}

✅ 关键点：

• 每次遇到 '1'，就说明发现一个新岛屿；
• 立即通过 DFS 将该岛屿所有相连陆地变为 '0'，避免重复计数；
• 本质是 “连通分量计数” 问题，DFS/BFS/并查集均可解。

---

📊 复杂度分析

• 时间复杂度：O(m × n)
  每个格子最多被访问一次（无论是 '1' 还是 '0'）。
• 空间复杂度：O(m × n)（最坏情况）
  • 递归栈深度在最坏情况下（全为 '1' 且呈蛇形）可达 m × n；
  • 若使用 BFS（队列），空间复杂度也为 O(min(m, n)) 到 O(mn)；
  • 若允许修改原数组，则无需额外 visited 数组。

💡 本解法直接修改原数组，节省了额外空间。

---

🧩 解题思路

核心思想：连通区域染色（Flood Fill）

• 将每个岛屿看作一个四连通的连通分量；
• 遍历网格，一旦发现未访问的陆地（'1'），就启动一次 “洪水填充”（Flood Fill）：
  • 把该连通区域所有 '1' 变成 '0'；
  • 同时计数器 +1。

为什么能避免重复计数？

因为 DFS 会一次性清除整个岛屿。后续遍历时，该岛屿所有位置都已变为 '0'，不会再被当作新岛屿。

边界处理技巧

• 在 DFS 开头统一判断：越界 or 是水 → 直接返回；
• 无需在调用前判断，代码更简洁。