深度解析算法之BFS解决FloodFill算法
外企中国路｜福特强化与中国合作伙伴关系 力挽销售颓势}
FloodFill中文是洪水灌溉 找出在区域中性质相同的联通块
79.图像渲染
题目链接
有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。你也被给予三个整数 sr , sc 和 color 。你应该从像素 image[sr][sc] 开始对图像进行上色 填充 。
为了完成 上色工作：
- 从初始像素开始，将其颜色改为
color。 - 对初始坐标的 上下左右四个方向上 相邻且与初始像素的原始颜色同色的像素点执行相同操作。
- 通过检查与初始像素的原始颜色相同的相邻像素并修改其颜色来继续 重复 此过程。
- 当 没有 其它原始颜色的相邻像素时 停止 操作。
最后返回经过上色渲染 修改 后的图像 。
示例 1:
输入： image = [[1,1,1],[1,1,0],[1,0,1] ]，sr = 1, sc = 1, color = 2
输出：[[2,2,2],[2,2,0],[2,0,1] ]
解释： 在图像的正中间，坐标 (sr,sc)=(1,1) （即红色像素）,在路径上所有符合条件的像素点的颜色都被更改成相同的新颜色（即蓝色像素）。
注意，右下角的像素 没有 更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。
示例 2:
输入： image = [[0,0,0],[0,0,0] ], sr = 0, sc = 0, color = 0
输出： [[0,0,0],[0,0,0] ]
解释： 初始像素已经用 0 着色，这与目标颜色相同。因此，不会对图像进行任何更改。
提示:
m == image.lengthn == image[i].length1 <= m, n <= 500 <= image[i][j], color < 2160 <= sr < m0 <= sc < n
题目给到了一个坐标，然后要求将这个坐标四周相连并且大小相等的格子进行染色的操作
class Solution
{
typedef pair<int,int> PII;//就是我们的坐标
//我们这里的数组就是我们x,y坐标周围的范围坐标，加上数组中的对应的大小就可以找到对应的位置了
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 prev=image[sr][sc];//标记下需要修改的像素值
if(prev==color)return image;//处理边界情况，如果选中的像素值和我们需要修改的像素值以一样的话，那么我们直接返回imag
int m=image.size(),n=image[0].size();
queue<PII>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++)//遍历4个方向
{
int x=a+dx[i],y=b+dy[i];
//我们这里必须保证我们的坐标是不越界的情况，我们才能将这个丢进我们的队列中去
if(x>=0&&x<m&&y>=0&&y<n&&image[x][y]==prev)//如果这个点的值的大小等于我们的prev的值的话，那么我们就将这个点加入到队列中去
{
q.push({x,y});
}
}
}
//当整个while循环结束之后，我们所有满足条件的位置都被填上了新的颜色了
return image;
}
};这里我们使用到了一个坐标组了，我们的(x,y)坐标加上对应的dx和dy获得到的就是我们当前点四周的坐标的位置
80.岛屿数量
题目链接
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入： grid = [ [“1”,“1”,“1”,“1”,“0”], [“1”,“1”,“0”,“1”,“0”], [“1”,“1”,“0”,“0”,“0”], [“0”,“0”,“0”,“0”,“0”] ] **输出：**1
示例 2：
输入： grid = [ [“1”,“1”,“0”,“0”,“0”], [“1”,“1”,“0”,“0”,“0”], [“0”,“0”,“1”,“0”,“0”], [“0”,“0”,“0”,“1”,“1”] ] 输出： 3
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]的值为'0'或'1'
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])//如果这个数等于1的话，并且没有遇到过的话
{
ret++;
bfs(grid,i,j);//将这块陆地全部都进行标记操作
//如果再次遍历到标记过的数的话，我们就不进行ret++操作了，不会重复标记了
}
}
}
return ret;
}
void bfs(vector<vector<char>>&grid,int i,int j)
{
queue<pair<int,int>>q;
q.push({i,j});//将(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];//那么这里的x和y就会随便遍历就变成我们上下左右的四个坐标了
if(x>=0&&y>=0&&x<m&&y<n&&grid[x][y]=='1'&&vis[x][y]==false)//只要这个位置没有遍历过的话
{
q.push({x,y});//将这个位置丢进去
vis[x][y]=true;//将这个位置状态进行改变操作
}
}
}
}
};就是一直进行遍历操作，看看这数是否遍历过，遍历过的话我们就给这个数加上一个true的状态，并且将四周的满足条件的数字都进行判断下
81.岛屿的最大面积
题目链接
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
示例 1：
输入： grid = [ [0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出： 6
解释： 答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
示例 2：
输入： grid = [[0,0,0,0,0,0,0,0] ] 输出： 0
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 50grid[i][j]为0或1
在正常的遍历的时候进行面积的统计操作，多一个变量
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]==false)//这个岛屿没有被统计过
{
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();//删除队头数据
//接下来开始从(a,b)这个位置开始向上下左右四个位置开始找满足条件的坐标了
for(int k=0;k<4;k++)
{
int x=a+dx[k],y=b+dy[k];
if(x>=0&&y>=0&&x<m&&y<n&&grid[x][y]==1&&vis[x][y]==false)//说明这个位置之前是没有遍历过的
{
q.push({x,y});//我们将这个位置添加到队列中去
vis[x][y]=true;
count++;//面积加一
}
}
}
return count;//将数据返回
}
};82.被围绕的区域
题目链接
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获 所有 被围绕的区域：
- **连接：**一个单元格与水平或垂直方向上相邻的单元格连接。
- 区域：连接所有
'O'的单元格来形成一个区域。 - **围绕：**如果您可以用
'X'单元格 连接这个区域，并且区域中没有任何单元格位于board边缘，则该区域被'X'单元格围绕。
通过 原地 将输入矩阵中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。你不需要返回任何值。
示例 1：
输入： board = [[“X”,“X”,“X”,“X”],[“X”,“O”,“O”,“X”],[“X”,“X”,“O”,“X”],[“X”,“O”,“X”,“X”] ]
输出：[[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“O”,“X”,“X”] ]
解释：
在上图中，底部的区域没有被捕获，因为它在 board 的边缘并且不能被围绕。
示例 2：
输入： board = [[“X”] ]
输出： [[“X”] ]
提示：
m == board.lengthn == board[i].length1 <= m, n <= 200board[i][j]为'X'或'O'
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();
//1.先处理边界上面的'O',全部修改成'.'
for(int j=0;j<n;j++)//我们的第一行的横坐标是0，j一直在变化
{
//这个是第一行
if(board[0][j]=='O')bfs(board,0,j);//将(0,j)这一行满足条件都修改为'.'
if(board[m-1][j]=='O')bfs(board,m-1,j);//这个是对最后一行的判断
}
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);//最后一列
}
//2.还原
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(board[i][j]=='O')board[i][j]='X';//如果围绕的话，那么就将O修改为X
else if(board[i][j]=='.')board[i][j]='O';//将边界的还原为'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')//如果满足条件的话就将这个位置进队里面
{
q.push({x,y});
board[x][y]='.';
}
}
}
//那么这个while循环结束之后就将与边界相连的区域都变成了'.'了
}
};我们先将第一行最后一行和第一列最后一列边界进行处理，如果边界上有’O’的话，那么我们就将这些’O’变成’.’ 处理完成这些边界情况之后，我们就进行还原操作，将整块面积中被’X’包围的’O’修改为’X’,但是如果是上面处理边界情况的结果’.'的话，那么我们就复原为’O’就行了
基本的BFS框架 让(x,y)这个位置进队列，然后对这个位置的数据进行修改，然后就开始我们的while循环将这个点四周的点都进行一个判断操作，入队删除并且修改
腾讯云开发者
