【算法】BFS-解决FloodFill问题

目录

FloodFill问题

图像渲染

岛屿数量

岛屿的最大面积

被围绕的区域

---

FloodFill问题

FloodFill就是洪水灌溉的意思，假设有下面的一块田地，负数代表是凹地，正数代表是凸地，数字的大小表示凹或者凸的程度。现在下一场大雨，请问大雨下完，这块田地会有几处积水

会发现会有3处积水，FloodFill问题的本质就是找到性质相同的连通块。所以可以使用dfs或者bfs解决。使用两种算法的原理是相同的，只是实现方法不同。

图像渲染

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

从给定的点开始宽搜，将周围等于给定的点的颜色全都改成目标颜色即可

class Solution {
public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {int m = image.size(), n = image[0].size();vector<vector<int>> v(m, vector<int>(n, 0));queue<pair<int, int>> q;q.push({sr, sc});v[sr][sc] = 1;int flag = image[sr][sc];int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};while(!q.empty()){int x = q.front().first, y = q.front().second;q.pop();image[x][y] = color;for(int i = 0;i < 4;i ++){int a = x + dx[i], b = y + dy[i];if(a >= 0 && a < m && b >= 0 && b < n && image[a][b] == flag && v[a][b] == 0) {q.push({a, b});v[a][b] = 1;}}}return image;}
};

并且要注意数组全是0，且flag也是0的情况，所以添加一个标记数组。不让一个元素重复放进队列 

岛屿数量

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

直接遍历一下二维数组，当遇到1时，就使用bfs将这个岛屿全部变成0，然后继续向后遍历二维数组，等到遍历完后，进行了几次bfs就有几个岛屿

class Solution {
public:int numIslands(vector<vector<char>>& grid) {int m = grid.size(), n = grid[0].size(), ans = 0;for(int i = 0;i < m;i ++)for(int j = 0;j < n;j ++)if(grid[i][j] == '1'){ans ++;bfs(grid, i, j, m, n);}return ans;}void bfs(vector<vector<char>>& grid, int x, int y, int m, int n){queue<pair<int, int>> q;int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};q.push({x, y});grid[x][y] = '0';while(!q.empty()){auto t = q.front();q.pop();for(int i = 0;i < 4;i ++){int a = t.first + dx[i], b = t.second + dy[i];if(a >= 0 && a < m && b >= 0 && b < n && grid[a][b] == '1'){q.push({a, b});grid[a][b] = '0';}}}}
};

岛屿的最大面积

695. 岛屿的最大面积 - 力扣（LeetCode）

直接遍历二维数组，当遇到1时，也就是遇到岛屿时，直接使用bfs将这个岛屿全部变成0，并在这期间计算出这个岛屿的面积，也就是每向队列中放入一个数据就++，然后最后返回，与答案比较

class Solution {
public:int maxAreaOfIsland(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size(), ans = 0;for(int i = 0;i < m;i ++)for(int j = 0;j < n;j ++)if(grid[i][j] == 1)ans = max(ans, dfs(grid, m, n, i, j));return ans;}int dfs(vector<vector<int>>& grid, int m, int n, int x, int y){queue<pair<int, int>> q;q.push({x, y});grid[x][y] = 0;int sum = 1;int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};while(!q.empty()){auto t = q.front();q.pop();for(int i = 0;i < 4;i ++){int a = t.first + dx[i], b = t.second + dy[i];if(a >= 0 && a < m && b >= 0 && b < n && grid[a][b] == 1){q.push({a, b});grid[a][b] = 0;sum ++;}}}return sum;}
};

被围绕的区域

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

这道题的重点是边缘的O是不算被X围绕的，而我们要找的是一个O的连通块，并且这个连通块里面全部的O都要被X围绕。所以，我们可以将与边缘的O连通的块排除，剩下的就都是被包围的

class Solution {
public:void solve(vector<vector<char>>& board) {// 遍历边界，若边界上的是O，则进行宽搜，将与这个O相连的所有O标记，被标记的O不会被变成Xint m = board.size(), n = board[0].size();vector<vector<int>> flag(m, vector<int>(n, 0));// 第一行for(int i = 0;i < n;i ++)if(board[0][i] == 'O')bfs(board, flag, m, n, 0, i);// 最后一行for(int i = 0;i < n;i ++)if(board[m - 1][i] == 'O')bfs(board, flag, m, n, m - 1, i);// 第一列for(int i = 1;i < m - 1;i ++)if(board[i][0] == 'O')bfs(board, flag, m, n, i, 0);// 最后一列for(int i = 1;i < m - 1;i ++)if(board[i][n - 1] == 'O')bfs(board, flag, m, n, i, n - 1);// 遍历一遍数组，当字符是O，并且flag数组中是0，说明这个是被X包含的for(int i = 0;i < m;i ++)   for(int j = 0;j < n;j ++)if(board[i][j] == 'O' && flag[i][j] == 0) board[i][j] = 'X';}void bfs(vector<vector<char>>& board, vector<vector<int>>& flag, int m, int n, int x, int y){queue<pair<int, int>> q;q.push({x, y});flag[x][y] = 1;int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};while(!q.empty()){auto t = q.front();q.pop();for(int i = 0;i < 4;i ++){int a = t.first + dx[i], b = t.second + dy[i];if(a >= 0 && a < m && b >= 0 && b < n && board[a][b] == 'O' && flag[a][b] == 0){q.push({a, b});flag[a][b] = 1;}}}}
};

要注意board数组全是O的情况，所以只有当标记数组为0才放进队列当中。不让一个元素重复放入队列