岛屿数量

题目描述

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

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

此外，你可以假设该网格的四条边均被水包围。

数据样例

示例 1：

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

  • $m == grid.length$
  • $n == grid[i].length$
  • $1 \leq m, n \leq 300$
  • grid[i][j] 的值为 '0' 或 '1'

深度优先搜索 DFS - $O(N ^ 2)$

深度优先搜索 DFS

对于二维网格中的每个 1，题目说：所有水平和竖直方向的相邻 1 连接起来构成一块岛屿。现在要求出岛屿的个数。

那么我们可以从每个 1 开始 向周围四个方向搜索，找到所有相邻的 1，即为一个岛屿。

  • 枚举所有的可能的 1 的位置，将岛屿找出来即可。

注意点：

  • 枚举过的位置，不能再次枚举，会重复计算：可以将搜索过的陆地 1 置为 0 即可

四个方向搜索

每次从当前位置向四周四个方向搜索一种常用的技巧是：方向数组

  • int dx[4] = {-1, 0, 0, 1};
  • int dy[4] = {0, -1, 1, 0};

那么每次遍历这个数组的 $4$ 个位置会得到：

  • $(-1, 0), (0, -1), (0, 1), (1, 0)$
  • 这刚好是 $4$ 个方向 $x, y$ 的变化

因此：遍历 $4$ 个方向只需要枚举数组：

  • $x + dx[i], y + dy[i]$ 即为下一个位置

时间复杂度 - $O(N ^ 2)$

  • 由于遍历过的位置不会第二次遍历，因此每个位置最多遍历两次，因此时间复杂度为 $O(N ^ 2)$

代码

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
32
33
34
35
36
func numIslands(grid [][]byte) int {
    // 或者数组大小
    n, m := len(grid), len(grid[0])
    // 初始化方向数组
    dx, dy = []int{-1, 0, 0, 1}, []int{0, -1, 1, 0}
    res := 0
    // 依次枚举，寻找为 1 的位置
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if grid[i][j] == '1' {
                // 对于每个 1 的位置，表示有一个岛屿
                res++
                // 找到所有这个岛屿的陆地，将其都置为 0，避免后续重复搜索
                dfs(grid, i, j, n, m)
            }
        }
    }
    return res
}

var dx, dy []int

func dfs(g [][]byte, x, y, n, m int) {
    g[x][y] = '0'
    // 通过枚举方向数组来实现枚举周围 4 个方向
    for i := 0; i < 4; i++ {
        // a, b 为下一个位置，周围的某个位置
        a, b := x + dx[i], y + dy[i]
        // 如果搜索到数组的边界外，则跳过
        if a < 0 || b < 0 || a >= n || b >= m { continue }
        // 如果搜索到 0 的话，则跳过，必须相邻的陆地，也就是 1
        if g[a][b] == '0' { continue }
        // DFS，继续搜索下一个位置
        dfs(g, a, b, n, m)
    }
}
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
class Solution {
public:
    const int dx[4] = {-1, 0, 0, 1};
    const int dy[4] = {0, -1, 1, 0};

    void dfs(vector<vector<char>>& g, int x, int y, int n, int m) {
        g[x][y] = '0';
        for (int i = 0; i < 4; ++i) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || b < 0 || a >= n || b >= m) continue;
            if (g[a][b] == '0') continue;
            dfs(g, a, b, n, m);
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == '1') {
                    ++res;
                    dfs(grid, i, j, n, m);
                }
            }
        }
        return res;
    }
};