树与图中等1 种解法

#200岛屿数量

统计字符网格中由上下左右相邻的陆地 1 组成的岛屿数量。

#矩阵#深度优先搜索#连通分量

解题主线

每次扫描到未访问的 1，就发现了一个新的连通分量，计数加一后用 DFS 淹没整座岛。

DFS 把访问过的 '1' 改为 '2'，后续扫描不会再次从同一岛屿启动。

计数发生在 DFS 起点，而不是每个陆地格子。

解法 1：DFS 淹没连通分量

扫描网格；每发现一块未访问陆地就增加岛屿数，并递归标记它的全部四连通陆地。

时间复杂度

O(mn)

空间复杂度

O(mn) 最坏，来自递归栈

200. 岛屿数量 · DFS 淹没连通分量

java

final class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;

        int islands = 0;
        for (int row = 0; row < grid.length; row++) {
            for (int column = 0; column < grid[0].length; column++) {
                if (grid[row][column] == '1') {
                    islands++;
                    flood(grid, row, column);
                }
            }
        }
        return islands;
    }

    private void flood(char[][] grid, int row, int column) {
        if (row < 0 || row >= grid.length || column < 0 || column >= grid[0].length) {
            return;
        }
        if (grid[row][column] != '1') return;

        grid[row][column] = '2';
        flood(grid, row - 1, column);
        flood(grid, row + 1, column);
        flood(grid, row, column - 1);
        flood(grid, row, column + 1);
    }
}

扫描网格；每发现一块未访问陆地就增加岛屿数，并递归标记它的全部四连通陆地。

边界与易错点

字符网格应比较 '1'，而不是整数 1。
原地标记会修改输入。
边界判断必须先于 grid[row][column] 访问。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/medium/Q_island_num_200.java