岛屿数量 图解题解

岛屿数量这道题在问什么

网格里每个格子要么是陆地字符 '1'，要么是海水字符 '0'。水平或竖直方向相邻的陆地连成一座岛，问一共有几座。用图论的话说，这是在数「陆地的连通分量个数」——彼此能通过上下左右走到的陆地算同一块。注意连通只认四个方向，斜对角挨着的两块陆地不算同一座岛，这个定义直接决定后面搜索时只往四个方向扩散。

为什么数岛屿要靠 DFS 洪水填充

逐格扫描很容易发现陆地，难的是别把同一座岛数成好几座——一座大岛横跨几十个格子，扫描时会撞上它几十次。关键观察由此而来：计数的单位是「岛」而不是「格」，所以第一次撞见某座岛时就该把它整个处理掉，让后续扫描再也撞不上它。

怎么「整个处理掉」？从这块陆地出发，向四个方向递归扩散，把所有连得上的陆地统统标记，这个过程像洪水从一点漫开淹没整片区域，所以也叫洪水填充（flood fill），用 DFS 或 BFS 实现都行。参考代码用 DFS 直接把走到的陆地改写成 '0'，形象地说就是把这座岛「沉」进海里。

沉岛操作维护着什么不变量

把数过的岛立刻沉掉，维护的是这样一条不变量：扫描指针之前经过的区域里，不存在任何还没计数的陆地。于是推论非常干净——扫描途中每撞见一个 '1'，它必然属于一座全新的、没数过的岛，放心加一，绝不会重复。

正确性的另一半是「不漏」：DFS 从起点扩散，恰好覆盖与起点连通的所有陆地，既不会漏掉本岛的格子（每个方向都探），也不会淹到别的岛（中间隔着海水，递归在 '0' 处止步）。一次沉岛动作与一座岛严格一一对应，计数自然准确。

递归的边界条件为什么这样写

dfs(i, j) 开头先做两个判断：下标越界直接返回；格子不是 '1'（是海水或已被沉掉）也直接返回。顺序不能反——必须先判越界再取值，否则会数组越界，在 Python 里负下标还会静悄悄绕到另一头，制造更隐蔽的错。过了这两关才把当前格改成 '0'，然后向四个方向递归。把「已访问」和「海水」统一表示成 '0'，让终止条件只剩一条，是这份代码简洁的来源。

复杂度分析与常见追问

时间 O(R×C)：每个格子至多被外层扫描看一次、被 DFS 进入一次，进入后就变 '0' 不会再进。空间 O(R×C)：最坏整张网格全是陆地，递归深度可达格子总数；担心递归栈溢出可以换成显式队列的 BFS，逻辑不变。

两个常见追问：不想破坏输入网格，就另开一个同尺寸的 visited 布尔数组，判断条件改成「是 '1' 且没访问过」，代价是 O(R×C) 额外空间；若进一步问最大岛屿面积（LeetCode 695），让 dfs 返回它沉掉的格子数，外层取最大值即可。

Python

def numIslands(grid):
    if not grid: return 0
    R, C = len(grid), len(grid[0])
    def dfs(i, j):
        if i < 0 or j < 0 or i >= R or j >= C: return
        if 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)            # 四个方向
    cnt = 0
    for i in range(R):
        for j in range(C):
            if grid[i][j] == '1':           # 遇到新陆地
                cnt += 1
                dfs(i, j)                   # 沉掉整座岛
    return cnt

Java

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int R = grid.length, C = grid[0].length, cnt = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (grid[i][j] == '1') {        // 遇到新陆地
                cnt++;
                dfs(grid, i, j);            // 沉掉整座岛
            }
        }
    }
    return cnt;
}
private void dfs(char[][] g, int i, int j) {
    if (i < 0 || j < 0 || i >= g.length || j >= g[0].length) return;
    if (g[i][j] != '1') return;             // 海水/已沉没
    g[i][j] = '0';                          // 沉掉这格
    dfs(g, i-1, j); dfs(g, i+1, j);
    dfs(g, i, j-1); dfs(g, i, j+1);         // 四个方向
}

C++

class Solution {
    void dfs(vector<vector<char>>& g, int i, int j) {
        int R = g.size(), C = g[0].size();
        if (i < 0 || j < 0 || i >= R || j >= C) return;
        if (g[i][j] != '1') return;          // 海水/已沉没
        g[i][j] = '0';                       // 沉掉这格
        dfs(g, i-1, j); dfs(g, i+1, j);
        dfs(g, i, j-1); dfs(g, i, j+1);      // 四个方向
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        int cnt = 0;
        for (int i = 0; i < (int)grid.size(); i++)
            for (int j = 0; j < (int)grid[0].size(); j++)
                if (grid[i][j] == '1') {     // 遇到新陆地
                    cnt++; dfs(grid, i, j);  // 沉掉整座岛
                }
        return cnt;
    }
};