这篇博客主要记录了使用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”。