XingHuiSamaの宝藏之地

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

‍
‍

1. 算法核心思想

本题旨在求解二维网格中的连通分量个数。采用深度优先搜索（DFS）结合“沉岛”策略是解决此类问题的标准做法。

其核心逻辑在于：遍历整个二维网格，每当扫描到一块陆地（'1'），即说明发现了一座新岛屿，此时岛屿总数加一。随后，立即以该节点为起点启动 DFS，将与该陆地相连的所有相邻陆地全部修改为水域（'0'）。这一“沉岛”操作可以确保在后续的网格遍历中，同一座岛屿的其余相连部分不会被重复计算。

2. 代码逻辑拆解

主函数 numIslands：利用双重循环顺序扫描整个二维网格。当条件 grid[i][j] == '1' 成立时，说明进入了一片未被记录的连通区域。此时调用 func 函数进行沉岛操作，并使岛屿计数器 islands 自增。
递归函数 func：负责具体执行连通区域的“淹没”与边界探索。
- 状态修改：首先将当前坐标点修改为 '0'。
- 边界判定与扩展：依次向上下左右四个方向探索。在发起下一步递归调用前，代码中加入了严格的边界条件判定（如 i - 1 >= 0、j + 1 < grid[0].size() 等）。这种前置判定策略保证了传入递归栈的坐标始终合法，避免了无效的越界调用开销。

‍

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int islands = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                    func(grid, i, j);
                    islands++;
                }
            }
        }

        return islands;
    }
    void func(vector<vector<char>>& grid, int i, int j) {
        if (grid[i][j] == '1') {
            grid[i][j] = '0';

            //shang
            if (i - 1 >= 0) {
                func(grid, i - 1, j);
            }
            if (i + 1 < grid.size()) {
                func(grid, i + 1, j);
            }
            if (j - 1 >= 0) {
                func(grid, i, j - 1);
            }
            if (j + 1 < grid[0].size()) {
                func(grid, i, j + 1);
            }
        }

    }
};

‍

3. 复杂度分析

时间复杂度：**** $O(M \times N)$

其中 $M$ 和 $N$ 分别为网格的行数和列数。虽然算法包含嵌套循环以及内部递归，但由于每个初值为 '1' 的单元格在首次被 DFS 访问后即被修改为 '0'，因此整张网格中的每个单元格最多仅被访问和处理常数次。
空间复杂度：**** $O(M \times N)$

算法的空间开销主要源于 DFS 的递归调用栈。在最坏情况下（例如整个网格均为相互连通的陆地），DFS 会持续向深层递归，调用栈的最大深度将达到 $M \times N$ 。

‍