关于FloodFill
关于FloodFill算法，我们之前在dfs章节已经介绍过了：算法学习（17）—— FloodFill算法-CSDN博客
下面是用bfs宽搜来解决的实例
部分OJ题详解
733. 图像渲染
733. 图像渲染 - 力扣（LeetCode）
- 题目是一样的，所以不论是dfs还是bfs，要解决的都是找到符合要求的一个联通块，我们之前是用的dfs，这次我们尝试用bfs来解决这道题
- 先找到题目给的坐标的点，然后每一层都往四个方向判断一次，假设第一层找到两个1，那么下一层就同时在这两个1再继续往外扩展，然后在扩展的过程中把1修改成2即可
- 代码编写也与dfs非常相似，只是把递归换成了循环而已
class Solution
{queue<pair<int, int>> q; //在层序遍历过程中存坐标int dx[4] = {0, 0, -1, 1};int dy[4] = {1, -1, 0, 0};int prev; //记录初始颜色int m, n;
public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {prev = image[sr][sc];m = image.size(), n = image[0].size();if(prev == color) return image; //如果颜色相同，直接返回q.push({sr, sc});while(q.size()){auto [a, b] = q.front(); //先取队头元素q.pop();image[a][b] = color;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) && image[x][y] == prev) q.push({x, y});}}return image;}
};200. 岛屿数量
200. 岛屿数量 - 力扣（LeetCode）
- 题目意思很简单，之前也已经讲过，使用bfs的思路和dfs是一样的，只需要对dfs的代码稍加修改即可
class Solution
{vector<vector<bool>> vis;int dx[4] = {0, 0, -1, 1};int dy[4] = {1, -1, 0, 0};int m, n;int ret = 0;queue<pair<int, int>> q;
public:int numIslands(vector<vector<char>>& grid) {m = grid.size(), n = grid[0].size();vis = vector<vector<bool>>(m, vector<bool>(n)); for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(!vis[i][j] && grid[i][j] == '1'){ret++;bfs(grid, i, j);}}}return ret;}void bfs(vector<vector<char>>& g, int i, int j) //作用是把与最开始位置连通的岛屿全部标记一下{vis[i][j] = true;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 && y >= 0) && (x < m && y < n) && (!vis[x][y] && g[x][y] == '1')){q.push({x, y});vis[x][y] = true;}}}}
};695. 岛屿的最大面积
695. 岛屿的最大面积 - 力扣（LeetCode）
- 思路是一样的，改一下dfs的代码即可
class Solution
{vector<vector<bool>> vis;int dx[4] = {0, 0, -1, 1};int dy[4] = {1, -1, 0, 0};int m, n;int count = 0;queue<pair<int, int>> q;
public:int maxAreaOfIsland(vector<vector<int>>& grid) {int ret = 0;m = grid.size(), n = grid[0].size();vis = vector<vector<bool>>(m, vector<bool>(n)); for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(!vis[i][j] && grid[i][j] == 1){bfs(grid, i, j);ret = max(ret, count);count = 0;}}}return ret;}void bfs(vector<vector<int>>& g, int i, int j) //作用是把与最开始位置连通的岛屿全部标记一下{vis[i][j] = true;q.push({i, j});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 && y >= 0) && (x < m && y < n) && (!vis[x][y] && g[x][y] == 1)){ q.push({x, y});count++;vis[x][y] = true;}}}}
};130. 被围绕的区域
130. 被围绕的区域 - 力扣（LeetCode）
class Solution {int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, -1, 1};int m, n;queue<pair<int, int>> q;
public:void solve(vector<vector<char>>& board) {m = board.size(), n = board[0].size();// 1，把与边界O相连的连通块修改成点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); // 修改最后一列}// 2，还原for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (board[i][j] == '.') board[i][j] = 'O';else if (board[i][j] == 'O') board[i][j] = 'X';}}}void bfs(vector<vector<char>>& board, int i, int j) {board[i][j] = '.';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 && y >= 0) && (x < m && y < n) && board[x][y] == 'O') { board[x][y] = '.';q.push({x, y});}}}}
};
