一“填”到底：深入理解Flood Fill算法
✨✨✨学习的道路很枯燥，希望我们能并肩走下来!
文章目录
目录
文章目录
前言
一 floodfill算法是什么？
二 相关OJ题练习
2.1 图像渲染
2.2 岛屿数量
2.3 岛屿的最大面积
2.4 被围绕的区域
2.5 太平洋大西洋水流问题
2.6 扫雷游戏
2.7 衣橱整理（原：面试题 13. 机器人的运动范围 ）
总结
前言
本篇详细介绍了进一步介绍floodfill算法，让使用者对floodfill算法有更加深刻的认知，而不是仅仅停留在表面，更好的模拟，为了更好的使用. 文章可能出现错误，如有请在评论区指正，让我们一起交流，共同进步！
一 floodfill算法是什么？
洪水填充(也称为种子填充)是一种算法，用于确定连接到多维数组中给定节点的区域。
可以用dfs或者bfs来作为基础，我们这里用DFS
floodfill的本质是搜索找到性质相同的一个连通块（区域）
二 相关OJ题练习
2.1 图像渲染
733. 图像渲染 - 力扣（LeetCode）
class Solution {
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int m,n,prev;
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
if(image[sr][sc] == color) return image;
prev = image[sr][sc];
m = image.size(),n = image[0].size();
dfs(image,sr,sc,color);
return image;
}
void dfs(vector<vector<int>>& image, int i, int j, int color)
{
image[i][j] = color;
for(int k = 0; k < 4;k++)
{
int x = i + dx[k], y = j + dy[k];
if(x >=0 && x < m && y >= 0 && y < n && image[x][y] == prev)
{
dfs(image,x,y,color);
}
}
}
};2.2 岛屿数量
200. 岛屿数量 - 力扣（LeetCode）
class Solution {
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int ret,m,n;
bool vis[301][301];
public:
int numIslands(vector<vector<char>>& grid) {
m = grid.size(),n = grid[0].size();
for(int i = 0;i<m;i++)
{
for(int j = 0;j<n;j++)
{
if(grid[i][j] == '1' && !vis[i][j])
{
dfs(grid,i,j);
ret++;
}
}
}
return ret;
}
void dfs(vector<vector<char>>& grid,int i,int j)
{
vis[i][j] = true;
for(int k = 0;k<4;k++)
{
int x = i + dx[k], y = j + dy[k];
if(x >=0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y])
{
vis[x][y] = true;
dfs(grid,x,y);
}
}
}
};2.3 岛屿的最大面积
695. 岛屿的最大面积 - 力扣（LeetCode）
class Solution {
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int ret,m,n,count;
bool vis[51][51];
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++)
{
if(grid[i][j] == 1 && !vis[i][j])
{
dfs(grid,i,j);
ret = max(ret,count);
count = 0;
}
}
}
return ret;
}
void dfs(vector<vector<int>>& grid,int i,int j)
{
count++;
vis[i][j] = true;
for(int k = 0;k<4;k++)
{
int x = i + dx[k], y = j + dy[k];
if(x >=0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y])
{
dfs(grid,x,y);
}
}
}
};2.4 被围绕的区域
130. 被围绕的区域 - 力扣（LeetCode）
逆转思维，直接从边界进行DFS，将符合条件的改成‘.’,在遍历一遍
class Solution {
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,-1,1};
int m,n;
public:
void solve(vector<vector<char>>& board) {
m = board.size(), n = board[0].size();
for(int j = 0;j<n;j++)
{
if(board[0][j] == 'O') dfs(board,0,j);
if(board[m-1][j] == 'O') dfs(board,m-1,j);
}
for(int i = 0;i<m;i++)
{
if(board[i][0] == 'O') dfs(board,i,0);
if(board[i][n-1] == 'O') dfs(board,i,n-1);
}
for(int i = 0;i<m;i++)
for(int j = 0;j<n;j++)
{
cout<<board[i][j]<<" ";
if(board[i][j] == '.') board[i][j] = 'O';
else if(board[i][j] == 'O') board[i][j] = 'X';
}
}
void dfs(vector<vector<char>>& board,int i,int j)
{
board[i][j] = '.';
for(int k = 0; k < 4; k++)
{
int x = i + dx[k], y = j + dy[k];
if(x >=0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
{
dfs(board,x,y);
}
}
}
};2.5 太平洋大西洋水流问题
417. 太平洋大西洋水流问题 - 力扣（LeetCode）
class Solution {
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
vector<vector<int>> ret;
int m,n;
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
m = heights.size(),n = heights[0].size();
vector<vector<bool>> visP(m,vector<bool>(n));
vector<vector<bool>> visA(m,vector<bool>(n));
for(int j = 0; j < n ;j++)
{
dfs(heights,0,j,visP);
dfs(heights,m-1,j,visA);
}
for(int i = 0; i < m; i++)
{
dfs(heights,i,0,visP);
dfs(heights,i,n-1,visA);
}
for(int i = 0;i < m; i++)
for(int j = 0; j < n; j++)
{
if(visP[i][j] && visA[i][j])
{
ret.push_back({i,j});
}
}
return ret;
}
void dfs(vector<vector<int>>& heights,int i, int j,vector<vector<bool>>& vis)
{
vis[i][j] = true;
for(int k = 0; k < 4; k++)
{
int x = i + dx[k], y = j + dy[k];
if(x >=0 && x < m && y >= 0 && y < n && heights[x][y] >= heights[i][j] && !vis[x][y])
{
dfs(heights,x,y,vis);
}
}
}
};2.6 扫雷游戏
529. 扫雷游戏 - 力扣（LeetCode）
class Solution {
int dx[8] = {1,-1,0,0,1,1,-1,-1};
int dy[8] = {0,0,1,-1,1,-1,1,-1};
int m,n;
public:
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click)
{
if(board[click[0]][click[1]] == 'M')
{
board[click[0]][click[1]] = 'X';
return board;
}
m = board.size(),n = board[0].size();
dfs(board,click[0],click[1]);
return board;
}
void dfs(vector<vector<char>>& board,int i,int j)
{
int count = 0;
for(int k = 0; k < 8; k++)
{
int x = i + dx[k], y = j + dy[k];
if(x >=0 && x < m && y >= 0 && y < n && board[x][y] == 'M')
{
count++;
}
}
if(count) //周围有地雷
{
board[i][j] = count + '0';
return;
}
else //周围没地雷
{
board[i][j] = 'B';
for(int k = 0; k < 8; k++)
{
int x = i + dx[k], y = j + dy[k];
if(x >=0 && x < m && y >= 0 && y < n && board[x][y] == 'E')
{
dfs(board,x,y);
}
}
}
}
};2.7 衣橱整理（原：面试题 13. 机器人的运动范围 ）
LCR 130. 衣橱整理 - 力扣（LeetCode）
class Solution {
int ret;
bool vis[101][101];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int _m,_n,_cnt;
public:
int wardrobeFinishing(int m, int n, int cnt) {
_m = m,_n = n, _cnt = cnt;
dfs(0,0);
return ret;
}
void dfs(int i,int j)
{
ret++;
vis[i][j] = true;
for(int k = 0; k < 4; k++)
{
int x = i + dx[k], y = j + dy[k];
if(x >=0 && x < _m && y >= 0 && y < _n && !vis[x][y] && check(x,y))
{
dfs(x,y);
}
}
}
bool check(int i,int j)
{
int tmp = 0;
while(i)
{
tmp += i % 10;
i /= 10;
}
while(j)
{
tmp += j % 10;
j /= 10;
}
return tmp <= _cnt;
}
};总结
✨✨✨各位读友，本篇分享到内容是否更好的让你理解floodfill算法，如果对你有帮助给个👍赞鼓励一下吧！！
🎉🎉🎉世上没有绝望的处境，只有对处境绝望的人。
感谢每一位一起走到这的伙伴，我们可以一起交流进步！！！一起加油吧！！