LeetCode 200. 岛屿数量

【LetMeFly】200.岛屿数量

力扣题目链接：https://leetcode.cn/problems/number-of-islands/

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

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

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

 

示例 1：

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

示例 2：

输入：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 <= m, n <= 300
• grid[i][j] 的值为 '0' 或 '1'

方法一：BFS

用广度优先搜索遍历一遍地图，遇到为'1'的方块就从开始广搜，并把答案的“岛屿数量”+1

广搜过程中，把遍历到的岛屿标记为'2'

一些广搜题列表可参考广度优先搜索题解专题，该专题主要包括图的广搜和二叉树的广搜。

• 时间复杂度$O(nm)$，其中地图的大小为$n\times m$
• 空间复杂度$O(M)$，其中$M$是最大的岛屿面积

AC代码

C++

int direction[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

class Solution {
private:
public:
    int numIslands(vector<vector<char>>& grid) {  // '2'表示遍历过的岛屿
        int n = grid.size(), m = grid[0].size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    ans++;
                    grid[i][j] = '2';
                    queue<pair<int, int>> q;
                    q.push({i, j});
                    while (q.size()) {
                        auto[x, y] = q.front();
                        q.pop();
                        for (int d = 0; d < 4; d++) {
                            int tx = x + direction[d][0];
                            int ty = y + direction[d][1];
                            if (tx >= 0 && tx < n && ty >= 0 && ty < m) {
                                if (grid[tx][ty] == '1') {
                                    grid[tx][ty] = '2';
                                    q.push({tx, ty});
                                }
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
};
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

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126400354