BFS算法篇——FloodFill问题的高效解决之道（下）

前言

上篇我们简要介绍了用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算法的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！