【LeetCode热题100】BFS解决FloodFill算法

这篇博客主要记录了使用BFS解决FloodFill算法的几道题目，包括图像渲染、岛屿数量、岛屿的最大面积、被包围的区域。

class Solution {using PII = pair<int, int>;
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});int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};while(q.size()){auto [x, y] = q.front();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] == prev){q.push({a, b});}}} return image;}
};

题目分析：对于这道题目，我们使用FloodFill算法去解决。首先，将image[sr][sc]上色，创建一个队列，队列元素为pair<int,int>，表示待上色元素的坐标，依次去遍历这个位置周围4个位置，看是不是需要上色，如果需要，那么把它放到队列中去，直到队列为空才停止。在遍历某一个位置时，设置int dx[4]={0,0,1,-1}和int dy[4]={1,-1,0,0}两个数组，依次去取对应位置组成当前位置坐标的偏移量。

class Solution {using PII = pair<int, int>;
public:int numIslands(vector<vector<char>>& grid) {int ret = 0;int m = grid.size(), n = grid[0].size();vector<vector<bool>> state(m, vector<bool>(n, false));queue<PII> q;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};for(int i = 0 ; i < m ; i++){for(int j = 0 ; j < n ; j++){if(grid[i][j] == '0' || state[i][j] == true) continue;q.push({i, j});while(q.size()){PII pos = q.front();q.pop();int x = pos.first, y = pos.second;state[x][y] = true;for(int k = 0 ; k < 4 ; k++){int a = x + dx[k], b = y + dy[k];if(a >= 0 && a < m && b >= 0 && b < n && state[a][b] == false && grid[a][b] == '1'){q.push({a, b});state[a][b] = true;}}}ret++;}}return ret;}
};

题目分析：这道题我们需要创建一个大小为m*n的数组state，表示当前位置有没有被遍历过。依次去遍历每一个位置，当遍历到一块陆地后，把与它相连的陆地找到，然后ret++，直到遍历完整个数组。

class Solution 
{using PII = pair<int, int>;bool state[51][51] = {false};int m;int n;int ret = 0;int dx[4] = {0, 0, 1, -1};int dy[4] = {1,-1, 0, 0};
public:int maxAreaOfIsland(vector<vector<int>>& grid) {m = grid.size(); n = grid[0].size();for(int i = 0 ; i < m ; i++){for(int j = 0 ; j < n ; j++){int count = bfs(grid, i, j);ret = max(ret, count);}}return ret;}int bfs(vector<vector<int>>& grid, int i, int j){if(grid[i][j] == 0 || state[i][j]) return 0;queue<PII> q;int count = 0;q.push({i,j});state[i][j] = true;while(q.size()){auto [x, y] = q.front();q.pop();count++;for(int i = 0 ; i < 4 ; i++){int a = x + dx[i];int b = y + dy[i];if(a >= 0 && a < m && b >= 0 && b < n && grid[a][b] == 1 && !state[a][b]){q.push({a, b});state[a][b] = true;}}} return count;}
};

题目分析：依次遍历每一块岛屿，在找到更大面积的岛屿后，更新ret。具体的思路和前面的题一样。

class Solution 
{int m , n;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};
public:void solve(vector<vector<char>>& board) {m = board.size(), n = board[0].size();for(int i = 0 ; i < n ; i++){if(board[0][i] == 'O') bfs(board, 0, i);if(board[m-1][i] == 'O') bfs(board, m-1, i);}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';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 [x,y] = q.front();q.pop();for(int k = 0 ; k < 4 ; k++){int a = x + dx[k];int b = y + dy[k];if(a >= 0 && a < m && b >= 0 && b < n && board[a][b] == 'O'){q.push({a, b});board[a][b] = '.';}}}}
};

题目分析：这道题由于边上的的“O”不是被围绕的区域，所以直接采用BFS不好处理。我们可以反着想，先处理边上的“O”区域，将其替换为“.”，然后扫描矩阵，如果遇到“O”则替换为“X”，如果遇到“.”则替换为“O”。