Number of Islands

200. 岛屿数量

分析

岛屿的定义
- '1' 表示陆地，'0' 表示水
- 一个岛屿是由相邻（水平或垂直方向）的 '1' 连续组成的一块区域
遍历网格
- 遍历网格中每个位置 (i, j)，若当前位置为 '1'，说明发现了一个新的岛屿：
- 执行深度优先搜索 dfs() 标记当前岛屿的所有陆地为 '*'，表示已访问
- 岛屿数量加 1
深度优先搜索dfs()
- 从当前陆地 (x, y) 出发，尝试向四个方向移动（上、下、左、右）
- 若移动后的位置仍为 '1' 且未越界，递归调用 dfs() 继续标记

时间复杂度

每个格子最多被访问一次，时间复杂度为 O(m * n)，其中 m 和 n 分别是网格的行数和列数

空间复杂度

递归栈深度取决于岛屿的最大面积，最坏情况下为 O(m * n)，即岛屿覆盖整个网格

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution
{
public:
    std::vector<std::vector<char>> g; // 全局保存网格
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // 四个方向

    int numIslands(vector<vector<char>>& grid)
    {
        g = grid; // 初始化网格
        int res = 0; // 岛屿数量
        for (int i = 0; i < g.size(); ++i)
            for (int j = 0; j < g[0].size(); ++j)
                if (g[i][j] == '1') // 找到未访问的陆地
                {
                    dfs(i, j); // 标记整个岛屿
                    ++res; // 岛屿数量加 1
                }
        return res;
    }

    void dfs(int x, int y)
    {
        g[x][y] = '*'; // 标记当前位置为已访问
        for (int i = 0; i < 4; ++i) // 尝试向四个方向移动
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < g.size() && b >= 0 && b < g[0].size() && g[a][b] == '1')
                dfs(a, b); // 若新位置是未访问的陆地，递归处理
        }
    }
};