200. 岛屿数量
给你一个由 '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
思路1:
使用DFS深度搜索,在外层用for循环遍历每个元素,一旦元素为‘1’则进入“新岛屿”,并在该个“新岛屿”做DFS深度搜索,将周围为“1”的都标记成“已经选择过”。最后记录进入“新岛屿的次数即可”
class Solution {
public:
//判断该坐标是否符合
bool isValid(vector<vector<char>>& grid,int row,int col)
{
if(row<0||col<0||row>=grid.size()||col>=grid[0].size()) return false;
return true;
}
//dfs将一个岛屿都标记为“已经选择过”
void dfs(vector<vector<char>>& grid,vector<vector<bool>>& valid,int row,int col)
{
if(!isValid(grid,row,col)||!valid[row][col]||grid[row][col]=='0') return;
valid[row][col]=false;
//对四个方向进行延深
if(isValid(grid,row+1,col)) dfs(grid,valid,row+1,col);
if(isValid(grid,row,col+1)) dfs(grid,valid,row,col+1);
if(isValid(grid,row-1,col)) dfs(grid,valid,row-1,col);
if(isValid(grid,row,col-1)) dfs(grid,valid,row,col-1);
}
int numIslands(vector<vector<char>>& grid) {
if(grid.size()==0) return 0;
vector<vector<bool>> valid(grid.size(),vector<bool>(grid[0].size(),true));
int ret=0;
for(int i=0;i<grid.size();i++)
{
for(int j=0;j<grid[0].size();j++)
{
if(grid[i][j]=='0'||!valid[i][j]) continue;
//dfs进行染色
dfs(grid,valid,i,j);
ret++;
}
}
return ret;
}
};
思路2:
广度搜索:用类似策略,只是用dfs代替了bfs文章来源:https://www.toymoban.com/news/detail-807934.html
class Solution {
public:
//判断该坐标是否符合
bool isValid(vector<vector<char>>& grid,int row,int col)
{
if(row<0||col<0||row>=grid.size()||col>=grid[0].size()) return false;
return true;
}
//bfs将一个岛屿都标记为“已经选择过”
void bfs(vector<vector<char>>& grid,vector<vector<bool>>& valid,int row,int col)
{
queue<pair<int,int>> q;
q.push(make_pair(row,col));
while(!q.empty())
{
pair<int,int> temp=q.front();
q.pop();
int temp_row=temp.first,temp_col=temp.second;
//染色
valid[temp_row][temp_col]=false;
if(isValid(grid,temp_row+1,temp_col)&&valid[temp_row+1][temp_col]&&grid[temp_row+1][temp_col]=='1') q.push(make_pair(temp_row+1,temp_col));
if(isValid(grid,temp_row,temp_col+1)&&valid[temp_row][temp_col+1]&&grid[temp_row][temp_col+1]=='1') q.push(make_pair(temp_row,temp_col+1));
if(isValid(grid,temp_row-1,temp_col)&&valid[temp_row-1][temp_col]&&grid[temp_row-1][temp_col]=='1') q.push(make_pair(temp_row-1,temp_col));
if(isValid(grid,temp_row,temp_col-1)&&valid[temp_row][temp_col-1]&&grid[temp_row][temp_col-1]=='1') q.push(make_pair(temp_row,temp_col-1));
}
}
int numIslands(vector<vector<char>>& grid) {
if(grid.size()==0) return 0;
vector<vector<bool>> valid(grid.size(),vector<bool>(grid[0].size(),true));
int ret=0;
for(int i=0;i<grid.size();i++)
{
for(int j=0;j<grid[0].size();j++)
{
if(grid[i][j]=='0'||!valid[i][j]) continue;
//bfs进行染色
bfs(grid,valid,i,j);
ret++;
}
}
return ret;
}
};
但以上代码会超时。。。代码中是从队列中取出节点再标记,改为将节点加入队列就立即标记文章来源地址https://www.toymoban.com/news/detail-807934.html
class Solution {
public:
//判断该坐标是否符合
bool isValid(vector<vector<char>>& grid,int row,int col)
{
if(row<0||col<0||row>=grid.size()||col>=grid[0].size()) return false;
return true;
}
//bfs将一个岛屿都标记为“已经选择过”
void bfs(vector<vector<char>>& grid,vector<vector<bool>>& valid,int row,int col)
{
queue<pair<int,int>> q;
q.push(make_pair(row,col));
//染色
valid[row][col]=false;
while(!q.empty())
{
pair<int,int> temp=q.front();
q.pop();
int temp_row=temp.first,temp_col=temp.second;
if(isValid(grid,temp_row+1,temp_col)&&valid[temp_row+1][temp_col]&&grid[temp_row+1][temp_col]=='1')
{
q.push(make_pair(temp_row+1,temp_col));
valid[temp_row+1][temp_col]=false;
}
if(isValid(grid,temp_row,temp_col+1)&&valid[temp_row][temp_col+1]&&grid[temp_row][temp_col+1]=='1')
{
q.push(make_pair(temp_row,temp_col+1));
valid[temp_row][temp_col+1]=false;
}
if(isValid(grid,temp_row-1,temp_col)&&valid[temp_row-1][temp_col]&&grid[temp_row-1][temp_col]=='1')
{
q.push(make_pair(temp_row-1,temp_col));
valid[temp_row-1][temp_col]=false;
}
if(isValid(grid,temp_row,temp_col-1)&&valid[temp_row][temp_col-1]&&grid[temp_row][temp_col-1]=='1')
{
q.push(make_pair(temp_row,temp_col-1));
valid[temp_row][temp_col-1]=false;
}
}
}
int numIslands(vector<vector<char>>& grid) {
if(grid.size()==0) return 0;
vector<vector<bool>> valid(grid.size(),vector<bool>(grid[0].size(),true));
int ret=0;
for(int i=0;i<grid.size();i++)
{
for(int j=0;j<grid[0].size();j++)
{
if(grid[i][j]=='0'||!valid[i][j]) continue;
//bfs进行染色
bfs(grid,valid,i,j);
ret++;
}
}
return ret;
}
};
到了这里,关于1.19 力扣中等图论的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!