BFS 解决 FloodFill 算法(C++)

本文主要是介绍BFS 解决 FloodFill 算法(C++)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

前言
一、概念
二、岛屿数量
- 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]='*';}}}}
};