一、经验总结
什么是FloodFill算法？
FloodFill算法是一种用于填充连通区域的算法，通常用于图像处理和计算机图形学中。它从给定的起始点开始，向周围相邻的像素进行扩散填充，直到遇到边界或者其他指定条件停止。
FloodFill算法还可以用于统计连通块的数量，求各连通块的面积等。
BFS解决FloodFill算法
当使用BFS解决FloodFill算法时，可以从一个起始点开始，逐步向外扩展，一层层地遍历并填充相邻的空白区域。
需要注意的点：
- 使用队列来辅助实现BFS
- 创建横纵坐标的变化量数组，可以方便地遍历相邻地四个方向
- 可以使用两种方法防止重复地入队列访问：1.直接修改原数组 2.创建visited数组标记访问；不管是哪种方法都需要在元素入队列时进行修改，以防止同层元素的重复访问
二、相关编程题
2.1 图像渲染
题目链接
题目描述
算法原理
编写代码
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(color == prev) return image;
int m = image.size(), n = image[0].size();
queue<PII> que;
que.push({sr,sc});
image[sr][sc] = color;
while(!que.empty())
{
auto [r, c] = que.front();
que.pop();
for(int i = 0; i < 4; ++i)
{
int x = r+dx[i], y = c+dy[i];
if(x>=0 && x<m && y>=0 && y<n && image[x][y]==prev)
{
que.push({x, y});
image[x][y] = color;
}
}
}
return image;
}
};
2.2 岛屿数量
题目链接
题目描述
算法原理
编写代码
class Solution {
typedef pair<int,int> PII;
vector<vector<bool>> visited;
int m, n;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
public:
int numIslands(vector<vector<char>>& grid)
{
m = grid.size(), n = grid[0].size();
visited.resize(m, vector<bool>(n, false));
int ret = 0;
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
if(grid[i][j]=='1' && !visited[i][j])
{
++ret;
BFS(grid, i, j);
}
}
}
return ret;
}
void BFS(vector<vector<char>>& grid, int sx, int sy)
{
queue<PII> que;
que.push({sx, sy});
visited[sx][sy] = true;
while(!que.empty())
{
auto [a, b] = que.front();
que.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&&grid[x][y]=='1'&&!visited[x][y])
{
que.push({x,y});
visited[x][y] = true;
}
}
}
}
};
2.3 岛屿的最大面积
题目链接
题目描述
算法原理
同上，只需要在BFS的过程中顺便统计一下陆地面积即可（同样是在入队列时统计面积，防止重复记录）。
编写代码
class Solution {
typedef pair<int,int> PII;
vector<vector<bool>> visited;
int m, n;
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();
visited.resize(m, vector<bool>(n, false));
int area_max = 0;
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
if(grid[i][j]==1 && !visited[i][j])
area_max = max(area_max, BFS(grid, i, j));
}
}
return area_max;
}
int BFS(vector<vector<int>>& grid, int sx, int sy)
{
int area = 0;
queue<PII> que;
que.push({sx, sy});
visited[sx][sy] = true;
++area;
while(!que.empty())
{
auto [a, b] = que.front();
que.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&&grid[x][y]==1&&!visited[x][y])
{
que.push({x,y});
visited[x][y] = true;
++area;
}
}
}
return area;
}
};
2.4 被围绕的区域
题目链接
题目描述
算法原理
编写代码
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();
//1.先将边界上的'O'连通块修改为'.'
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 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);
}
//2.将剩下的'O'改为'X'，边界上的'.'改回'O'
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
if(board[i][j] == 'O') board[i][j] = 'X';
if(board[i][j] == '.') board[i][j] = 'O';
}
}
}
void BFS(vector<vector<char>>& board, int sx, int sy)
{
queue<pair<int,int>> que;
que.push({sx, sy});
board[sx][sy] = '.';
while(!que.empty())
{
auto [a,b] = que.front();
que.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&&board[x][y]=='O')
{
que.push({x,y});
board[x][y] = '.';
}
}
}
}
};
