LeetCode 200. 岛屿数量(搜索)
LeetCode 200. 岛屿数量(搜索)
SakuraTears
发布于 2022-01-13 14:01:45
发布于 2022-01-13 14:01:45
题目
给你一个由 '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 gridi 的值为 '0' 或 '1'
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-of-islands 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
经典搜索例题，找到为'1'的点然后遍历别的点。 每遍历一次岛屿数量++
BFS
class Solution {
public:
void BFS(int i, int j, vector<vector<char>>& grid) {
grid[i][j] = '0';
queue<vector<int>> q;
vector<int> n;
n.push_back(i);
n.push_back(j);
q.push(n);
while (! q.empty()) {
n.clear();
n = q.front();
q.pop();
i = n[0];
j = n[1];
if (j - 1 >= 0 && grid[i][j - 1] == '1') {
n.clear();
n.push_back(i);
n.push_back(j - 1);
grid[i][j - 1] = '0';
q.push(n);
}
if (i + 1 < grid.size() && grid[i + 1][j] == '1') {
n.clear();
n.push_back(i + 1);
n.push_back(j);
grid[i + 1][j] = '0';
q.push(n);
}
if (j + 1 < grid[i].size() && grid[i][j + 1] == '1') {
n.clear();
n.push_back(i);
n.push_back(j + 1);
grid[i][j + 1] = '0';
q.push(n);
}
if (i - 1 >= 0 && grid[i -1][j] == '1') {
n.clear();
n.push_back(i - 1);
n.push_back(j);
grid[i - 1][j] = '0';
q.push(n);
}
}
}
int numIslands(vector<vector<char>>& grid) {
int num = 0;
for (int i = 0; i < grid.size(); i++) {
for ( int j = 0; j < grid[i].size(); j++) {
if (grid[i][j] == '1') {
num++;
BFS(i, j, grid);
}
}
}
return num;
}
};DFS
class Solution {
public:
void DFS(int i, int j, vector<vector<char>>& grid) {
grid[i][j] = '0';
if (j - 1 >= 0 && grid[i][j - 1] == '1') DFS(i, j - 1, grid);
if (i + 1 < grid.size() && grid[i + 1][j] == '1') DFS(i + 1, j, grid);
if (j + 1 < grid[i].size() && grid[i][j + 1] == '1') DFS(i, j + 1, grid);
if (i - 1 >= 0 && grid[i -1][j] == '1') DFS(i - 1, j, grid);
}
int numIslands(vector<vector<char>>& grid) {
int num = 0;
for (int i = 0; i < grid.size(); i++) {
for ( int j = 0; j < grid[i].size(); j++) {
if (grid[i][j] == '1') {
num++;
DFS(i, j, grid);
}
}
}
return num;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021年01月30日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
