BFS解决FloodFill算法

1.图像渲染

733. 图像渲染 - 力扣（LeetCode）

1.题目解析

有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。你也被给予三个整数 sr , sc 和 color 。你应该从像素 image[sr][sc] 开始对图像进行上色填充。

为了完成 上色工作：

从初始像素开始，将其颜色改为 color。
对初始坐标的 上下左右四个方向上 相邻且与初始像素的原始颜色同色的像素点执行相同操作。
通过检查与初始像素的原始颜色相同的相邻像素并修改其颜色来继续重复此过程。
当没有其它原始颜色的相邻像素时停止操作。

最后返回经过上色渲染修改后的图像。

2.示例

示例 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，因为它不是在上下左右四个方向上与初始点相连的像素点。

3.解题思路

------本题使用的方法BFS,还有方向坐标int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0};

参数：
- color：新填充颜色，用于替换与起始点颜色不同的区域。
- sr 和 sc：起始点的行和列索引。
- image：输入图像，是一个二维整数矩阵，其中每个元素表示像素值。
检查起始点颜色是否与新颜色相同，如果相同，直接返回原始图像。
获取图像的行数 m 和列数 n。
初始化一个队列 q，将起始点 (sr, sc) 入队。
当队列不为空时，执行 BFS 遍历：
- 弹出队列头部的点，获取当前点的坐标 (a, b)。
- 检查当前点的颜色，如果已经是新颜色，跳过。
- 将新颜色赋值给当前点。
- 遍历当前点的四个方向，如果相邻点在图像范围内且颜色与起始点相同，将其加入队列。

4.代码实现

class Solution {typedef pair<int , int> PII;//定义方向变量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;int m = image.size(), n = image[0].size();queue<PII> q;q.push({sr , sc});while(! q.empty()){auto [a , b] = q.front();image [a][b] = color;q.pop();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.岛屿数量

200. 岛屿数量 - 力扣（LeetCode）

1.题目解析

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

2.示例

示例 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

3.解题思路

遍历整个矩阵，每次找到「⼀块陆地」的时候：

• 说明找到「⼀个岛屿」，记录到最终结果 ret ⾥⾯；

• 并且将这个陆地相连的所有陆地，也就是这块「岛屿」，全部「变成海洋」。这样的话，我们下次遍历到这块岛屿的时候，它「已经是海洋」了，不会影响最终结果。

• 其中「变成海洋」的操作，可以利⽤「深搜」和「宽搜」解决，其实就是733.图像渲染这道题~

bfs 方法：
- 使用 queue 实现广度优先搜索。
- 将起始点 (i, j) 入队，并标记为已访问。
- 当队列不为空时，循环处理队列中的点。
- 对于每个点，检查四个方向的相邻单元格。
- 如果相邻单元格在网格范围内、未访问过、且值为 '1'，则将其加入队列，并标记为已访问。
numIslands 方法：
- 初始化岛屿数量 ret 为 0。
- 遍历网格的每个单元格，对于值为 '1' 的单元格，如果未访问过，则调用 bfs 方法进行搜索，并增加岛屿计数。
- 返回计算得到的岛屿数量。

4.代码实现

class Solution {int m, n;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};bool visi[301][301];public:void bfs(vector<vector<char>>& grid , int i, int j){queue<pair<int , int>> q;q.push({i , j});visi[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 && !visi[x][y] && grid[x][y] == '1'){q.push({x , y});visi[x][y] = true;}}}}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' && !visi[i][j]){ret++;bfs(grid, i ,j);}}return ret;}
};

3.岛屿的最大面积

1.题目解析

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

2.示例

示例 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

3.解题思路

1.与第二道例题岛屿数量类似，只需定义一个计数器，来计算个数。

2.注意方向变量（dx、dy）的使用

3.还要让visi进行赋值

4.代码实现

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

4.被围绕的区域

130. 被围绕的区域 - 力扣（LeetCode）

1.题目解析

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获所有 被围绕的区域：

连接：一个单元格与水平或垂直方向上相邻的单元格连接。
区域：连接所有 'O' 的单元格来形成一个区域。
围绕：如果您可以用 'X' 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 'X' 单元格围绕。

通过原地将输入矩阵中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。你不需要返回任何值。

2.示例

示例 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"]]

3.解题思路

正难则反。可以先利⽤ bfs 将与边缘相连的 '0' 区域做上标记，然后重新遍历矩阵，将没有标记过的 '0' 修改成 'X' 即可。

4.代码实现

class Solution {int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;
public: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] = '.';}}}}void solve(vector<vector<char>>& board) {//将靠近边上的字符'O'转换成字符‘.’m = board.size(), n = board[0].size();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++){if(board[i][0] == 'O') bfs(board, i, 0);if(board[i][n - 1] == 'O') 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';}}}
};