BFS 解决 FloodFill 算法(C++)

作者 : admin 本文共1913个字,预计阅读时间需要5分钟 发布时间: 2024-06-10 共2人阅读

文章目录

  • 前言
  • 一、概念
  • 二、岛屿数量
    • 1.题目链接
    • 2.算法原理
    • 3.代码编写
  • 三、被围绕的区域
    • 1.题目链接
    • 2.算法原理
    • 3.代码编写
  • 总结

前言

一、概念

BFS就是广度优先遍历,也就是层序遍历。
FloodFill是指在数组中找出性质相同的连通块,并根据题目进行操作。

二、岛屿数量

1.题目链接

200. 岛屿数量

2.算法原理

遍历整个矩阵,每找到一块陆地,记录一次。
我们怎末知道我们是否已经遍历过这个地方了呢??

方法1:如果遍历了,我们修改原数组,将1变为0
方法2:用一个bool数组,如果遍历过了,我们设为true.

3.代码编写

class Solution {
public:
bool vision[301][301]={false};
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int m;
int n;
int numIslands(vector<vector<char>>& grid) 
{
m=grid.size();
n=grid[0].size();
//记录个数
int total=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
//1才为陆地,并且没有被访问
if(grid[i][j]=='1'&&vision[i][j]==false)
{
total++;
bfs(grid,i,j);
}
}
}
return total;
}
void bfs(vector<vector<char>>& grid,int a,int b) 
{
queue<pair<int,int>>q;
q.push({a,b});
vision[a][b]=true;
while(!q.empty())
{
auto[x1,y1]=q.front();
q.pop();
for(int k=0;k<4;k++)
{
int x=x1+dx[k];
int y=y1+dy[k];
if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]=='1'&&vision[x][y]==false)
{
q.push({x,y});
vision[x][y]=true;
}
}
}
}  
};

用全局遍历,可以避免大量的传参。
注意:auto[x1,y1]=q.front();这种写法
int dx[4]={0,0,-1,1}; int dy[4]={1,-1,0,0};定义四个维度

三、被围绕的区域

1.题目链接

130. 被围绕的区域

2.算法原理

我们如果直接做的话,进行bfs,首先判断是否边界为O,再进行bfs将O设置为X。

我们可以用其他方法:正难则反

1.我们先处理边界,将边界为O的那块设为*(也可以用其他字符)
2.重新遍历,进行恢复。
如果是O,就变为X
如果是*,就变为O

3.代码编写

class Solution {
public:
int m;
int n;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void solve(vector<vector<char>>& board) 
{
m=board.size();
n=board[0].size();
//先处理边界情况
for(int i=0;i<m;i++)
{
if(board[i][0]=='O')
{
bfs(board,i,0);
}
if(board[i][n-1]=='O')
{
bfs(board,i,n-1);
}
}
for(int j=0;j<n;j++)
{
if(board[0][j]=='O')
{
bfs(board,0,j);
}
if(board[m-1][j]=='O')
{
bfs(board,m-1,j);
}
}
//还原
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(board[i][j]=='O')
{
board[i][j]='X';
}
if(board[i][j]=='*')
{
board[i][j]='O';
}
}
}
}
void bfs(vector<vector<char>>& board,int a,int b)
{
queue<pair<int,int>>q;
q.push({a,b});
board[a][b]='*';
while(!q.empty())
{
auto[a,b]=q.front();
q.pop();
for(int k=0;k<4;k++)
{
int x=a+dx[k];
int y=b+dy[k];
if(x>=0&&x<m&&y>=0&&y<n&&board[x][y]=='O')
{
q.push({x,y});
board[x][y]='*';
}
}
}
}
};

总结

以上就是今天要讲的内容 。希望对大家的学习有所帮助,仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~ 😘 😘 😘

本站无任何商业行为
个人在线分享-虚灵IT资料分享 » BFS 解决 FloodFill 算法(C++)
E-->