# 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
3
4
5
6
7

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

1
2
3
4
5
6
7

提示：

1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

# 思路

注意题目中每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成，斜方向相邻不算连接。例如示例 2 中就是三座岛：

本题的思路是：遇到一块没有遍历过的陆地，计数器加一，然后把这块陆地能够到达的所有陆地都标记为已访问。之后遇到海水或访问过的陆地就直接跳过，计数器最终就是岛屿数量。

那么如何把一块陆地能够到达的所有陆地标记出来？DFS、BFS 都可以。

# 深度优先搜索

DFS 从当前陆地出发，不断沿上下左右继续搜索，直到遇到边界、海水或访问过的陆地。

很多录友会疑惑：为什么有些 DFS 写了递归终止条件，有些却没有？区别只在判断的位置：

可以进入递归后，先判断当前位置是否合法，不合法就返回；
也可以在调用递归之前判断下一个位置是否合法，合法才递归。

这里采用第二种写法。只要调用 DFS，传入的位置就一定是没有访问过的陆地。

# 广度优先搜索

BFS 同样可以把一座岛的全部陆地标记出来，但有一个特别容易踩的坑：

只要节点加入队列，就代表已经访问，必须立刻标记；不能等到节点出队时再标记。

如果等出队才标记，同一个陆地可能被多个相邻节点重复加入队列：

这个细节看起来只差一行代码的位置，却可能让搜索产生大量重复入队。

# 模拟过程

以示例 2 为例，扫描到左上角第一块陆地时，答案加一。一次 DFS 或 BFS 会把左上角相连的四块陆地全部标记。

继续扫描时，中央的单独陆地和右下角的两块相连陆地分别触发一次搜索，所以最终共有三座岛。对角线相邻不算连通，方向数组中只有上下左右四个方向。

# 解题代码

class Solution {
private:
    int directions[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
        for (auto& direction : directions) {
            int nextX = x + direction[0];
            int nextY = y + direction[1];
            if (nextX < 0 || nextX >= grid.size() ||
                nextY < 0 || nextY >= grid[0].size()) {
                continue;
            }
            if (!visited[nextX][nextY] && grid[nextX][nextY] == '1') {
                visited[nextX][nextY] = true;
                dfs(grid, visited, nextX, nextY);
            }
        }
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
        int result = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    ++result;
                    visited[i][j] = true;
                    dfs(grid, visited, i, j);
                }
            }
        }
        return result;
    }
};

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

BFS 版本的区别只在于搜索函数：

class Solution {
private:
    int directions[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
        queue<pair<int, int>> que;
        que.push({x, y});
        visited[x][y] = true; // 入队就标记，避免重复入队

        while (!que.empty()) {
            auto [curX, curY] = que.front();
            que.pop();
            for (auto& direction : directions) {
                int nextX = curX + direction[0];
                int nextY = curY + direction[1];
                if (nextX < 0 || nextX >= grid.size() ||
                    nextY < 0 || nextY >= grid[0].size()) {
                    continue;
                }
                if (!visited[nextX][nextY] && grid[nextX][nextY] == '1') {
                    visited[nextX][nextY] = true;
                    que.push({nextX, nextY});
                }
            }
        }
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
        int result = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    ++result;
                    bfs(grid, visited, i, j);
                }
            }
        }
        return result;
    }
};

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
37
38
39
40
41
42

# 复杂度分析

时间复杂度：O(m × n)，每个网格最多访问一次。
空间复杂度：O(m × n)，visited、递归栈或 BFS 队列最坏都可能达到 O(m × n)。

# 其他语言

# Python3

class Solution:
    def numIslands(self, grid):
        rows, cols = len(grid), len(grid[0])

        def dfs(x, y):
            if x < 0 or x >= rows or y < 0 or y >= cols or grid[x][y] != "1":
                return
            grid[x][y] = "0"
            dfs(x - 1, y)
            dfs(x + 1, y)
            dfs(x, y - 1)
            dfs(x, y + 1)

        result = 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1":
                    result += 1
                    dfs(i, j)
        return result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Java

class Solution {
    public int numIslands(char[][] grid) {
        int result = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    result++;
                    dfs(grid, i, j);
                }
            }
        }
        return result;
    }

    private void dfs(char[][] grid, int x, int y) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] != '1') {
            return;
        }
        grid[x][y] = '0';
        dfs(grid, x - 1, y);
        dfs(grid, x + 1, y);
        dfs(grid, x, y - 1);
        dfs(grid, x, y + 1);
    }
}

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

# Go

func numIslands(grid [][]byte) int {
    rows, cols := len(grid), len(grid[0])
    var dfs func(int, int)
    dfs = func(x, y int) {
        if x < 0 || x >= rows || y < 0 || y >= cols || grid[x][y] != '1' {
            return
        }
        grid[x][y] = '0'
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y-1)
        dfs(x, y+1)
    }

    result := 0
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if grid[i][j] == '1' {
                result++
                dfs(i, j)
            }
        }
    }
    return result
}