LeetCode 200. 岛屿数量

题目描述

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

岛屿总是被水包围，并且每座岛屿只能由水平方向和竖直方向上相邻的陆地连接形成。

你可以假设网格的四条边都被水包围。

示例分析

示例 1

输入:
grid = [
  ['1','1','1','1','0'],
  ['1','1','0','1','0'],
  ['1','1','0','0','0'],
  ['0','0','0','0','0']
]
​
输出: 1

这个网格中所有陆地都连在一起，所以只有 1 座岛屿。

示例 2

输入:
grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]
​
输出: 3

这里可以分成三块互不相连的陆地，所以有 3 座岛屿。

解题思路

这道题的本质，其实就是在一个二维网格中统计连通块的数量。

每一块连续的 '1' 都可以看作一座独立的岛屿。

所以我们的思路很自然：

1. 遍历整个网格

2. 每当遇到一个还没有访问过的 '1'，说明发现了一座新的岛屿

3. 然后从这个位置出发，用 DFS 把和它相连的所有陆地全部访问一遍

4. 整个 DFS 结束后，这座岛屿就处理完了，答案加 1

你给出的代码正是这个思路。

核心思想

为什么遇到一个 '1' 就可以让答案加一

因为我们在遍历网格时，如果当前位置还是 '1'，说明它：

• 是陆地

• 并且之前还没有被访问过

那么它一定是某一座新岛屿的起点。

此时我们就从这里出发，把整座岛屿的所有陆地都遍历一遍，并标记成已访问状态。

这样后面再次遍历到这座岛屿里的其他位置时，就不会重复计数了。

所以：

每发现一个新的 '1'，就说明发现了一座新的岛屿。

为什么要“淹没”整座岛

如果我们只把当前这个格子处理掉，而不继续向四周扩展，那么同一座岛上的其他 '1' 在后续遍历时还会再次被当成新岛屿，结果就会重复计数。

所以当我们找到一块陆地后，必须把与它连通的所有陆地都一起处理掉。

这一步通常叫做：

• DFS 遍历

• Flood Fill（洪水填充）

• 染色

• 淹没岛屿

本质上都是一个意思。

代码实现

class Solution {
    private int res;
​
    public int numIslands(char[][] grid) {
        res = 0;
        for (int i = 0; i < grid.length; i ++) {
            for (int j = 0; j < grid[0].length; j ++) {
                if (grid[i][j] == '1') {
                    dfsGrid(grid, i, j);
                    res ++;
                }
            }
        }
        return res;
    }
​
    private void dfsGrid(char[][] grid, int row, int col) {
        if (row >= grid.length || col >= grid[0].length || row < 0 || col < 0) {
            return;
        }
        if (grid[row][col] != '1') {
            return;
        }
        grid[row][col] = '2';
        dfsGrid(grid, row - 1, col);
        dfsGrid(grid, row + 1, col);
        dfsGrid(grid, row, col - 1);
        dfsGrid(grid, row, col + 1);
    }
}

代码解析

1. 定义结果变量

private int res;

res 用来记录岛屿的数量。

每发现一座新的岛屿，就让它加 1。

2. 遍历整个网格

for (int i = 0; i < grid.length; i ++) {
    for (int j = 0; j < grid[0].length; j ++) {

我们需要把整个二维网格的每一个位置都检查一遍。

因为岛屿可能出现在任意位置。

3. 遇到 '1' 就开始 DFS

if (grid[i][j] == '1') {
    dfsGrid(grid, i, j);
    res ++;
}

这里非常关键。

如果当前位置是 '1'，说明这是一个还没有处理过的陆地。 那么它一定属于某一座新的岛屿。

于是：

1. 调用 dfsGrid(grid, i, j)，把整座岛屿都遍历并标记掉

2. res++，岛屿数量加一

4. DFS 的边界判断

if (row >= grid.length || col >= grid[0].length || row < 0 || col < 0) {
    return;
}

如果当前坐标越界了，就直接返回。

这一步是 DFS 的基本边界条件。

5. 不是陆地就返回

if (grid[row][col] != '1') {
    return;
}

如果当前位置不是 '1'，说明它可能是：

• '0'：水

• '2'：已经访问过的陆地

这两种情况都不需要继续 DFS，所以直接返回。

6. 标记当前陆地为已访问

grid[row][col] = '2';

这里把 '1' 改成 '2'，表示这个位置已经访问过了。

这样后面再次遍历到这里时，就不会重复统计。

你这里用 '2' 做标记，其实也可以用别的字符，比如 '0'。 本质都是一样的：让它不再被当成新的陆地处理。

7. 向四个方向扩展

dfsGrid(grid, row - 1, col);
dfsGrid(grid, row + 1, col);
dfsGrid(grid, row, col - 1);
dfsGrid(grid, row, col + 1);

从当前位置继续向：

• 上

• 下

• 左

• 右

四个方向搜索。

因为题目规定岛屿只通过水平和竖直方向连接，所以这里只需要搜四个方向，不需要搜对角线。

示例推演

我们用这个例子来模拟：

grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]

初始时：

res = 0

第一次找到 '1'

在 (0,0) 位置发现 '1'：

res = 1

然后从 (0,0) 出发 DFS，把左上角这一整块岛屿都标记为 '2'：

[
  ['2','2','0','0','0'],
  ['2','2','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]

第二次找到 '1'

继续遍历，来到 (2,2)，发现新的 '1'：

res = 2

DFS 后变成：

[
  ['2','2','0','0','0'],
  ['2','2','0','0','0'],
  ['0','0','2','0','0'],
  ['0','0','0','1','1']
]

第三次找到 '1'

继续遍历，来到 (3,3)，发现新的 '1'：

res = 3

DFS 会把 (3,3) 和 (3,4) 一起标记掉：

[
  ['2','2','0','0','0'],
  ['2','2','0','0','0'],
  ['0','0','2','0','0'],
  ['0','0','0','2','2']
]

最终答案就是：

3

为什么这题适合用 DFS

因为每发现一块陆地，我们都需要把和它相连的所有陆地一次性找出来。

这种“从一个点出发，把整个连通区域全部搜完”的问题，就是 DFS 最擅长处理的场景。

当然，这题也可以用 BFS 或并查集来做，但 DFS 是最直观、最容易写的一种方法。

复杂度分析

假设网格大小为 m × n。

时间复杂度

O(m × n)

因为每个格子最多只会被访问一次。

虽然 DFS 看起来有递归，但不会让同一个位置被反复处理，所以总时间复杂度仍然是线性的。

空间复杂度

O(m × n)

最坏情况下，整个网格都是陆地，递归深度可能达到 m × n，因此递归栈空间最坏是 O(m × n)。

如果不考虑递归栈，只看额外变量，那么额外空间是 O(1)。

和 BFS 解法对比

这道题除了 DFS 之外，也可以用 BFS 来做。

DFS

优点：

• 代码简洁

• 思路直接

• 非常适合这种“连通块”问题

缺点：

• 递归过深时可能有栈溢出的风险

BFS

优点：

• 不用递归

• 更适合特别大的网格

缺点：

• 需要额外队列，代码稍微长一点

在 LeetCode 这道题里，DFS 是最常见、也最推荐掌握的写法。

总结

这道题的核心思路其实非常清楚：

1. 遍历整个网格

2. 每当遇到一个新的 '1'，说明发现了一座新的岛屿

3. 立刻用 DFS 把这座岛屿的所有陆地都标记掉

4. 避免后续重复统计

5. 最终统计一共发现了多少次新的 '1'

所以你可以把这道题记成一句话：

遍历网格，遇到陆地就 DFS 淹掉整座岛，同时答案加一。

这类题在后面经常会反复出现，比如：

• 岛屿的最大面积

• 被围绕的区域

• 腐烂的橘子

• 朋友圈 / 连通分量问题

所以这道题是非常经典的二维网格 DFS 入门题，值得彻底吃透。