leetcode-岛屿数量

点击:题目链接:给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。

思路

使用深度优先搜索。然后配合剪枝,即标记已扫描过的陆地。
搜索的条件就是一块陆地的上下左右是不是有相连的陆地,如果都没有,则判断该陆地为一座岛,如果有则继续搜索。

由于陆地的默认标记为‘1’, 故我们可以标记已经搜索的陆地为‘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
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {


for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[i].size(); ++j) {
if (findIsland(grid, i, j)) {
++count;
}
}
}
return count;
}

bool findIsland(vector<vector<char>>& grid, int indexi, int indexj) {
if (indexi == grid.size() || indexi<0) return false;
else if (indexj == grid[indexi].size() || indexj<0) return false;

if (grid[indexi][indexj] == '0' || grid[indexi][indexj] == '2') return false;

grid[indexi][indexj] = '2';

findIsland(grid, indexi+1, indexj);
findIsland(grid, indexi, indexj + 1);
findIsland(grid, indexi - 1, indexj);
findIsland(grid, indexi, indexj - 1);

return true;
}

private:
int count = 0;
};

复杂度

时间:O(MN), 空间: O(MN)

思路二

使用并查集

作者

Dylan Zhu

发布于

2021-04-17

更新于

2021-04-17

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...