一“填”到底：深入理解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;}
};