前言
上篇我们简要介绍了用BFS算法解决FloodFill问题，本篇我们将结合具体题目，进一步深化对于该算法的理解运用。
一. 图像渲染
1.1 题目链接：https://leetcode.cn/problems/flood-fill/description/
1.2 题目分析：
- 有一个m*n的二维数组表示图像，其中的值代表颜色
- 给出起始坐标和目标颜色，要求与起点相接并且值相同的所有像素点的值，都改为给定color的值
- 遍历方向为上下左右
1.3 思路讲解：
结合上篇内容很容易联想到使用bfs算法，但是在上下左右四个方向遍历时，可以通过初始化两个数组，大大简化步骤。
如图，将二维数组映射在平面直角坐标系内，上下左右四个方向的坐标变化如下。
之后我们按照层序遍历的方式，将各个顶点依次入队列，并按照上下左右的方向遍历判断即可。
1.4 代码实现：
class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
int prev=image[sr][sc];
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
int m=image.size();//行
int n=image[0].size();//列
if(prev==color)
{
return image;
}//处理特殊情况
queue<pair<int,int>> q;
q.push({sr,sc});
while(q.size())
{
auto [a,b]=q.front();
q.pop();
image[a][b]=color;
//下一层入队列
//处理边界情况
for(int i=0;i<4;i++)
{
int x=a+dx[i],y=b+dy[i];
if(x>=0&&x<m&&y>=0&&y<n&&image[x][y]==prev)
{
q.push({x,y});
}
}
}
return image;
}
};
二. 岛屿数量
2.1 题目链接：https://leetcode.cn/problems/number-of-islands/description/
2.2 题目分析：
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。（不考虑斜侧方向，只考虑水平和竖直）
此外，你可以假设该网格的四条边均被水包围。
2.3 思路讲解：
岛屿与上题的上色问题类似，都要求一个点内附近相接的同属性点。
通俗来讲，即一大块相接且被0围住的1，即代表一块岛屿。
因此，我们可以遍历数组内的每一个点，如果为1，则说明此处有一个岛屿，使用bfs算法将其周围的1全部转化为0
注意：本题并未提到原数组是否可以更改，因此我们为了以防万一，可以通过标记数组的方式进行1的转换。
2.4 代码实现：
class Solution {
public:
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
bool vis[301][301]={0};
int m,n;
int ret=0;//岛屿数量
void bfs(vector<vector<char>>& gird,int i,int j)
{
queue<pair<int,int>> q;
q.push({i,j});
vis[i][j]=true;
while(q.size())
{
auto [a,b]=q.front();
q.pop();
for(int k=0;k<4;k++)
{
int x=a+dx[k],y=b+dy[k];
if(x>=0&&x<m&&y>=0&&y<n&&vis[x][y]==0&&gird[x][y]=='1')
{
q.push({x,y});
vis[x][y]=true;
}
}
}
}
int numIslands(vector<vector<char>>& grid) {
m=grid.size(),n=grid[0].size();
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(grid[i][j]=='1'&&vis[i][j]==0)
{
ret++;
bfs(grid,i,j);
}
}
}
return ret;
}
};
三. 岛屿的最大面积
3.1 题目链接：https://leetcode.cn/problems/max-area-of-island/description/
3.2 题目分析：
- 岛屿的规则与上相同
- 本题要求返回岛屿的最大面积，而非岛屿的数量
3.3 思路讲解：
大体思路与上题相同，只需要记录下遍历过程中最大的岛屿面积，并在最终返回即可。
3.4 代码实现：
class Solution {
public:
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
bool vis[51][51]={false};//标记数组
int m,n;
int ret=0;//最大面积
int bfs(vector<vector<int>>& grid,int i,int j)
{
int count=1;//记录该岛屿面积
queue<pair<int,int>> q;
q.push({i,j});
vis[i][j]=true;
while(q.size())
{
auto [a,b]=q.front();
q.pop();
for(int k=0;k<4;k++)
{
int x=a+dx[k],y=b+dy[k];
if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1&&vis[x][y]==0)
{
q.push({x,y});
count++;
vis[x][y]=true;
}
}
}
return count;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
m=grid.size(),n=grid[0].size();
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(grid[i][j]==1&&vis[i][j]==0)
{
int temp=bfs(grid,i,j);
ret=max(ret,temp);
}
}
}
return ret;
}
};
四. 被围绕的区域
4.1 题目链接：https://leetcode.cn/problems/surrounded-regions/description/
4.2 题目分析：
- 给定一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ 组成，捕获所有被围绕的区域
- 围绕区域指被X包围的O
- 捕获指将O替换为X
4.3 思路讲解：
- 首先需要明确，最外层的O由于没有被X包围，因此是永远不会被替换的
- 因此被替换的只有边界内的O
所以我们只需要利用BFS算法遍历并替换即可。
注意：由于BFS算法在上下左右遍历时，可能存在边界上有O的情况，处理起来较为复杂。我们可以采取正难则反的思路。
在遍历之前，将边界上所有的O转化为*
4.4 代码实现：
class Solution {
public:
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int m,n;
void bfs(vector<vector<char>>& board,int i,int j)
{
queue<pair<int,int>> q;
q.push({i,j});
while(q.size())
{
auto [a,b]=q.front();
q.pop();
for(int k=0;k<4;k++)
{
int x=a+dx[k],y=b+dy[k];
if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='O')
{
q.push({x,y});
board[x][y]='*';
}
}
}
}
void solve(vector<vector<char>>& board) {
m=board.size(),n=board[0].size();
//遍历最上和最下两行
for(int j=0;j<n;j++)
{
if(board[0][j]=='O')
{
board[0][j]='*';
bfs(board,0,j);
}
if(board[m-1][j]=='O')
{
board[m-1][j]='*';
bfs(board,m-1,j);
}
}
//遍历最左和最右两列
for(int i=0;i<m;i++)
{
if(board[i][0]=='O')
{
board[i][0]='*';
bfs(board,i,0);
}
if(board[i][n-1]=='O')
{
board[i][n-1]='*';
bfs(board,i,n-1);
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(board[i][j]=='O')
{
board[i][j]='X';
}
else if(board[i][j]=='*')
{
board[i][j]='O';
}
}
}//还原操作
}
};
小结
本篇关于BFS算法的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！
