岛屿数量 | 每日算法 · 变量语义法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

给你一个由 '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. 遍历每个格子，遇到 '1' 就启动一次 DFS/BFS 把整个岛「淹没」。

2. 淹没操作：从该点出发向四个方向递归，把遇到的 '1' 都改成 '0'。

3. 每启动一次淹没就 ans++，因为这说明发现了一个新岛屿。

4. 原地修改 grid 代替 visited 数组，节省空间。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`grid[r][c]`	char	定义：当前位置的地形（'1'=未访问陆地, '0'=水或已访问）维护：访问陆地后置为 '0'（原地标记）更新：每次 DFS/BFS 进入时 grid[r][c] = '0'
`dirs`	int[][]	定义：四方向偏移量维护：不变量 `[(0,1),(0,-1),(1,0),(-1,0)]` 更新：不更新
`ans`	int	定义：岛屿总数维护：每次发现未访问陆地时 ans++ 更新：DFS/BFS 启动时 ans++

⌨️ 落码步骤

1. 双重循环遍历 grid，遇到 '1' 时 ans++ 并启动 DFS

2. DFS(r,c)：若越界或 grid[r][c] != '1'，直接返回

3. grid[r][c] = '0'（标记已访问）

4. 对四个方向递归 DFS

💻 代码实现

class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0

        def dfs(r, c):
            if r < 0 or r >= m or c < 0 or c >= n:
                return
            if grid[r][c] != '1':
                return
            grid[r][c] = '0'  # 淹没
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        for r in range(m):
            for c in range(n):
                if grid[r][c] == '1':
                    ans += 1
                    dfs(r, c)

        return ans

class Solution {
    int m, n;
public:
    int numIslands(vector>& grid) {
        m = grid.size(), n = grid[0].size();
        int ans = 0;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == '1') {
                    ans++;
                    dfs(grid, r, c);
                }
            }
        }
        return ans;
    }

    void dfs(vector>& grid, int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != '1')
            return;
        grid[r][c] = '0';
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }
};
// 时间 O(mn)，空间 O(mn)（递归栈）

📈 复杂度分析

时间复杂度 O(mn)

空间复杂度 O(mn)（DFS 栈）/ O(min(m,n))（BFS 队列）

⚠️ 常见坑

❗ DFS 越界检查必须在 grid[r][c] 检查之前，否则会越界访问。

❗ 原地修改 grid 后要确认题目是否允许修改输入。如果不允许，需要额外 visited 数组。

❗ Java/C++ 递归可能栈溢出（特别大的岛屿），改用 BFS 或迭代栈。

🔍 必测边界 Case

Case 1：空网格

grid = [] → 输出 0

Case 2：全是水

grid = [["0","0"],["0","0"]] → 输出 0