"绝境之中才窥见，Winner，Winner"
FloodFill算法简介:
floodfill又翻译成漫水填充。我们可以将下面的矩阵理解为一片具有一定高度的坡地，此时突发洪水，洪水会将高度<0的地方填满。
话句话来说，FloodFill算法是为了找出那些具有相同性质的区域。那我们现在就来看看一些经典的使用floodfill算法的题目。
图像渲染
(1) 题目解析 
这类题目的代码部分，都是将模拟的过程转化成代码。
(2) 算法代码
dfs:
class Solution {
public:
int m,n;
int prev;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
m = image.size(),n = image[0].size();
if(image[sr][sc] == color) return image;
prev = image[sr][sc];
dfs(image,sr,sc,color);
return image;
}
void dfs(vector<vector<int>>& image, int i,int j,int newcolor)
{
// 从这一点出发，每一个方向去 递归相邻节点
image[i][j] = newcolor;
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,newcolor);
}
}
}
};bfs:
class Solution {
public:
typedef pair<int,int> PII;
int m,n;
int prev;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
m = image.size(),n = image[0].size();
if(image[sr][sc] == color) return image;
// 当前位置会被修改为newcolor 这里是保存需要被渲染的值
prev = image[sr][sc];
bfs(image,sr,sc,color);
return image;
}
void bfs(vector<vector<int>>& image, int i,int j,int newcolor)
{
queue<PII> que;
image[i][j] = newcolor;
que.push({i,j});
while(que.size())
{
// 取出已经被渲染的位置，并将它的相邻位置，满足条件的 插入进队列
auto [a,b] = que.front();
que.pop();
for(int k=0;k<4;++k)
{
int x=a+dx[k],y=b+dy[k];
if(x>=0 && x<m && y>=0 && y<n && image[x][y] == prev)
{
image[x][y] = newcolor;
que.push({x,y});
}
}
}
}
};岛屿数量
(1) 题目解析 
注: 进行bfs或dfs时需要注意，防止统计已经遍历过的位置。我们有两种解决方法，其一就是对原数组内部的值进行修改，区别于目标条件，其二就是创建一个新的布尔数组，标记每一个遍历过的点。
(2) 算法代码
dfs:
class Solution {
public:
int m,n;
bool vis[301][301];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int numIslands(vector<vector<char>>& grid) {
m = grid.size(),n = grid[0].size();
int count = 0;
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
{
// 遍历到岛屿进行一次dfs 并且这个位置没有被访问过
if(grid[i][j] == '1' && !vis[i][j])
{
count++;
vis[i][j] = true; // 标记
dfs(grid,i,j);
}
}
return count;
}
void dfs(vector<vector<char>>& grid,int i,int j)
{
// 这里的dfs 只需将与(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 && grid[x][y] == '1' && !vis[x][y])
{
vis[x][y] = true;
dfs(grid,x,y);
}
}
}
};bfs:
class Solution {
public:
int m,n;
bool vis[301][301];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int numIslands(vector<vector<char>>& grid) {
m = grid.size(),n = grid[0].size();
int count = 0;
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
{
// 遍历到岛屿进行一次dfs 并且这个位置没有被访问过
if(grid[i][j] == '1' && !vis[i][j])
{
count++;
vis[i][j] = true; // 标记
bfs(grid,i,j);
}
}
return count;
}
void bfs(vector<vector<char>>& grid,int i,int j)
{
// 这里的bfs 只需将与(i,j) 相连的岛屿统计即可
// bfs通常需要借助队列来实现
queue<pair<int,int>> que;
que.push({i,j});
while(que.size())
{
auto [a,b] = que.front();
que.pop();
for(int k=0;k<4;++k)
{
int x=a+dx[k],y=b+dy[k];
if(x>=0 && x<m && y>=0 && y<n && grid[x][y] == '1' && !vis[x][y])
{
vis[x][y] = true;
que.push({x,y});
}
}
}
}
};岛屿的最大面积
(1) 题目解析 
这道题和上个题目十分类似，只不过这道题目的结果是求这些岛屿的最大面积，所以，我们需要对相连岛屿数量进行统计，并最终返回一个最大值。
(2) 算法代码
dfs:
class Solution {
public:
int m,n;
bool vis[301][301];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int ret,count;
int maxAreaOfIsland(vector<vector<int>>& grid) {
m = grid.size(),n = grid[0].size(),ret = 0;
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
{
// 遍历到岛屿进行一次dfs 并且这个位置没有被访问过
if(grid[i][j] == 1 && !vis[i][j])
{
count = 0;
dfs(grid,i,j);
ret = max(ret,count);
}
}
return ret;
}
void dfs(vector<vector<int>>& grid,int i,int j)
{
vis[i][j] = true;
count++;
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);
}
}
}
};bfs:
class Solution {
public:
int m,n;
bool vis[301][301];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int ret,count;
int maxAreaOfIsland(vector<vector<int>>& grid) {
m = grid.size(),n = grid[0].size(),ret = 0;
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
{
// 遍历到岛屿进行一次dfs 并且这个位置没有被访问过
if(grid[i][j] == 1 && !vis[i][j])
{
count = 0;
vis[i][j] = true; // 标记
bfs(grid,i,j);
ret = max(ret,count);
}
}
return ret;
}
void bfs(vector<vector<int>>& grid,int i,int j)
{
// 这里的bfs 只需将与(i,j) 相连的岛屿统计即可
// bfs通常需要借助队列来实现
queue<pair<int,int>> que;
que.push({i,j});
count++;
while(que.size())
{
auto [a,b] = que.front();
que.pop();
for(int k=0;k<4;++k)
{
int x=a+dx[k],y=b+dy[k];
if(x>=0 && x<m && y>=0 && y<n && grid[x][y] == 1 && !vis[x][y])
{
count++;
vis[x][y] = true;
que.push({x,y});
}
}
}
}
};被围绕的区域
(1) 题目解析
但其实，我们发现这两个dfs本质是做同样的事情，但却因为判断边界，我们需要写两份不同的dfs，这是蛮麻烦的事情。我们换个思路，直接用一个dfs将边界的'O'，进行过滤，并填上不相关的字符，再将整个数组遍历，遇到‘O’改为‘X’，遇到这个不相关的字符，改为'O'。
(2) 算法代码
dfs:
class Solution {
public:
int m,n;
bool vis[201][201];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
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)
{
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);
}
}
}
};bfs:
class Solution {
public:
int m,n;
bool vis[201][201];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
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') bfs(board,0,j);
if(board[m-1][j] == 'O') bfs(board,m-1,j);
}
// 第一列 最后一列
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 i=0;i<m;++i)
for(int j=0;j<n;++j)
{
if(board[i][j] == '.') board[i][j] = 'O';
else if(board[i][j] == 'O') board[i][j] = 'X';
}
}
void bfs(vector<vector<char>>& board,int i,int j)
{
board[i][j] = '.';
queue<pair<int,int>> que;
que.push({i,j});
while(que.size())
{
auto [a,b] = que.front();
que.pop();
for(int k=0;k<4;++k)
{
int x=a+dx[k],y=b+dy[k];
if(x>=0 && x<m && y>=0 && y<n && board[x][y] == 'O')
{
board[x][y] = '.';
que.push({x,y});
}
}
}
}
};扫雷
(1) 题目解析 
经典的扫雷游戏，至于玩法也就不过多解释。该题目考察的地方就在于，点击一个点之后，从这个 点开始进行对相邻领域的展开，我们可以采用dfs或bfs完成。
当挖出的位置是一个雷，将这个位置标记成‘X’，游戏结束。当挖出的一个地方是空位置，你需要首先去相邻区域查找是否有雷，如果没有发现雷，则标记为'B'，否则就需要将搜查到的雷的个数，标记在该位置处。
(2) 算法代码
dfs:
class Solution {
public:
int m,n;
bool vis[51][51];
// 扫雷位置有八个位置需要被展开
int dx[8] = {0,0,-1,1,-1,1,-1,1};
int dy[8] = {1,-1,0,0,1,-1,-1,1};
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
m = board.size(),n = board[0].size();
int i = click[0],j = click[1];
if(board[i][j] == 'M')
board[i][j] = 'X';
else
dfs(board,i,j);
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';
}
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);
}
}
}
};bfs:
class Solution {
public:
int m,n;
bool vis[51][51];
// 扫雷位置有八个位置需要被展开
int dx[8] = {0,0,-1,1,-1,1,-1,1};
int dy[8] = {1,-1,0,0,1,-1,-1,1};
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
m = board.size(),n = board[0].size();
int i = click[0],j = click[1];
if(board[i][j] == 'M')
board[i][j] = 'X';
else
bfs(board,i,j);
return board;
}
void bfs(vector<vector<char>>& board,int i,int j)
{
queue<pair<int,int>> que;
que.push({i,j});
vis[i][j] = true;
while(que.size())
{
auto [a,b] = que.front();
que.pop();
int count = 0;
// 统计雷的数量
for(int k=0;k<8;++k)
{
int x=a+dx[k],y=b+dy[k];
if(x>=0 && x<m && y>=0 && y<n && board[x][y] == 'M') count++;
}
if(count){
board[a][b] = count + '0';
}
else{
board[a][b] = 'B';
for(int k=0;k<8;++k)
{
int x=a+dx[k],y=b+dy[k];
if(x>=0 && x<m && y>=0 && y<n && board[x][y] == 'E')
{
// 这里改为'B' 避免被其他点统计到 队列中去
// 也可以使用 vis[x][y] = ture; 进行标记 不被统计 ！！！
board[x][y] = 'B';
que.push({x,y});
}
}
}
}
}
};本篇到此结束，感谢你的阅读。
祝你好运，向阳而生~
