leetcode岛屿的个数:广度优先搜索(BFS)
题目:
岛屿的个数
给定一个由 '1'
(陆地)和 '0'
(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
解体思路:这是一道标准的广度优先搜索题,可以尝试用递归的方法或者非递归的方法。比较重要的一点就是要进行边界检查:因为网格是给定的,所以在BFS过程中要保证每个节点都是有效没有越界的。
- 递归方法:
比较简单,直接上代码
//递归方法
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if(grid.size()==0)return 0;
int ans=0;
//获取行数和列数
rows=grid.size();
cols=grid[0].size();
//初始化访问标记数组
vector<vector<bool> > visited(rows,vector<bool>(cols,0));
//遍历寻找陆地点
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
//如果是陆地点且没有访问过就从这一点开始bfs广度优先搜索
if(grid[i][j]=='1'&&visited[i][j]==false)
{
ans++;//岛屿计数加1
bfs(grid,visited,i,j);
}
}
}
return ans;
}
private:
int rows;//行数
int cols;//列数
void bfs(vector<vector<char>>& grid,vector<vector<bool>>& visited,int i,int j)//广度优先搜索
{
if(i>=0&&i<rows&&j>=0&&j<cols)//网格的边界条件,不能越界
{
if(grid[i][j]=='1'&&visited[i][j]==false)
{
visited[i][j]=true;
//四个邻接点递归bfs
bfs(grid,visited,i+1,j);
bfs(grid,visited,i-1,j);
bfs(grid,visited,i,j-1);
bfs(grid,visited,i,j+1);
}
}
else return ;
}
};
- 非递归的方法
BFS的非递归方法需要借助队列来实现(FIFO的特性非常适合BFS),除bfs()函数之外的部分代码和递归方法的是一样的,只是bfs()的实现方式不同:
//非递归方法
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if(grid.size()==0)return 0;
int ans=0;
//获取行数和列数
rows=grid.size();
cols=grid[0].size();
//初始化访问标记数组
vector<vector<bool> > visited(rows,vector<bool>(cols,0));
//遍历寻找陆地点
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
//如果是陆地点且没有访问过就从这一点开始bfs广度优先搜索
if(grid[i][j]=='1'&&visited[i][j]==false)
{
ans++;//岛屿计数加1
bfs(grid,visited,i,j);
}
}
}
return ans;
}
private:
int rows;//行数
int cols;//列数
void bfs(vector<vector<char>>& grid,vector<vector<bool>>& visited,int i,int j)//广度优先搜索
{
queue<pair<int,int>> q;//队列保存邻接点
q.push(make_pair(i,j));
while(!q.empty())
{
int curr_i,curr_j;
curr_i=q.front().first;
curr_j=q.front().second;
q.pop();
//将邻接点加入队列中
q_push(grid,visited,q,curr_i-1,curr_j);
q_push(grid,visited,q,curr_i+1,curr_j);
q_push(grid,visited,q,curr_i,curr_j-1);
q_push(grid,visited,q,curr_i,curr_j+1);
}
}
//因为添加到队列需要一些条件判断,为了代码简洁,写了一个内联函数
inline void q_push(vector<vector<char>>& grid,vector<vector<bool>>& visited,queue<pair<int,int>> &q,int i,int j)
{
if(i>=0&&i<rows&&j>=0&&j<cols)//网格的边界条件,不能越界
{
if(grid[i][j]=='1'&&visited[i][j]==false)
{
visited[i][j]=true;
//四个邻接点递归bfs
q.push(make_pair(i,j));
}
}
}
};