BFS解决FloodFill算法相关leetcode算法题

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

文章目录

1.图像渲染
2.岛屿数量
3.岛屿的最大面积
4.被围绕的区域

1.图像渲染

图像渲染
在这里插入图片描述

class Solution {int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};
public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {int m = image.size(), n = image[0].size();int prev = image[sr][sc];//保存一下先前的像素值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.岛屿数量

岛屿数量
在这里插入图片描述

class Solution {int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};bool vis[301][301];//标志数组，用于标记某一个点是否已经访问过int m,n;
public:int numIslands(vector<vector<char>>& grid) {m = grid.size(), n = grid[0].size();int ret = 0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]=='1' && !vis[i][j]){ret++;bfs(grid,i,j);//将这一块区域都标记一下}}}return ret;}void bfs(vector<vector<char>>& grid,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();//注意这里是拷贝不能是引用，因为引用的话，递归调用会修改a,b的值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]){q.push({x,y});vis[x][y] = true;}}}}
};

3.岛屿的最大面积

岛屿的最大面积
在这里插入图片描述

class Solution {int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};bool vis[51][51];int m,n;
public:int maxAreaOfIsland(vector<vector<int>>& grid) {m = grid.size(),n = grid[0].size();int ret = 0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]== 1 &&!vis[i][j]){ret = max(ret,bfs(grid,i,j));}}}return ret;}int bfs(vector<vector<int>>& grid,int i,int j){int count = 0;queue<pair<int,int>> q;q.push({i,j});vis[i][j] = true;count++;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]){count++;q.push({x,y});vis[x][y] = true;}}}return count;}
};

4.被围绕的区域

被围绕的区域
在这里插入图片描述

class Solution {int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int m,n;
public:void solve(vector<vector<char>>& board) {m=board.size(),n = board[0].size();//先处理边界上的'0'连通块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';else if(board[i][j]=='.') board[i][j]='O';}}}void bfs(vector<vector<char>>& board,int i,int j){queue<pair<int,int>> q;q.push({i,j});board[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'){board[x][y] = '.';q.push({x,y});}}}}
};