floodfill，翻译为洪水灌溉，而floodfill算法本质上是为了解决在矩阵中性质相同的联通块问题。
一、图像渲染
. - 力扣（LeetCode）
class Solution {
public:
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int prev;//记住初始值
int m,n;
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
{
//先考虑边界条件，如果对应位置和color是一样的，那么直接返回
if(image[sr][sc]==color) return image;
m=image.size(),n=image[0].size();
prev=image[sr][sc];
dfs(image,sr,sc,color);
return image;
}
void dfs(vector<vector<int>>& image, int i, int j, int color) //直接用引用，在矩阵上修改
{
//第一步，将当前位置修改成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);
}
}
};二、岛屿问题
. - 力扣（LeetCode）
class Solution {
public:
int ret=0;
bool check[300][300];
int m,n;
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(!check[i][j]&&grid[i][j]=='1')//该数没被选过并且为1
{
++ret;//说明找到一块岛屿
dfs(grid,i,j);//然后让dfs去相邻位置将对应的子块给标记成true
}
}
return ret;
}
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void dfs(vector<vector<char>>& grid,int i,int j)
{
//首先先把当前位置标记成选过
check[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&&!check[x][y]&&grid[x][y]=='1')
dfs(grid,x,y);//继续去下一个位置找
}
}
};三、岛屿的最大面积
. - 力扣（LeetCode）
class Solution {
public:
bool check[50][50];
int m,n;
int count;//数每个字块的岛屿数量
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int maxAreaOfIsland(vector<vector<int>>& grid)
{
m=grid.size(),n=grid[0].size();
int ret=0;
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
if(!check[i][j]&&grid[i][j]==1)
{
count=0;//重置count
dfs(grid,i,j);
ret=max(ret,count);
}
return ret;
}
void dfs(vector<vector<int>>& grid,int i,int j)
{
++count;
check[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&&!check[x][y]&&grid[x][y]==1)
{
dfs(grid,x,y);
}
}
}
};四、被围绕的区域
. - 力扣（LeetCode）
class Solution {
public:
//正难则反，先去找边界
//1先找到边界的o，然后用dfs去找 找到了就修改成.
//2此时矩阵里的o肯定是在区域内的了，直接遍历一遍矩阵修改即可，顺便把.修改成圈
int m,n;
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);
}
//此时剩下位置的O给他改成X，然后.复原成O
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';
}
}
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
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);
}
}
};五、太平洋大西洋水流问题
. - 力扣（LeetCode）
class Solution {
public:
//思路，正难则反，用两个标记数组去标记两个大洋的位置
int m,n;
vector<vector<int>> ret;//记录返回值
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
vector<vector<int>> pacificAtlantic(vector<vector<int>>& h)
{
m=h.size(),n=h[0].size();
//设置两个标记数组
vector<vector<bool>> pac(m,vector<bool>(n));
auto atl=pac;
//先去找pac
for(int j=0;j<n;++j) dfs(h,0,j,pac);
for(int i=0;i<m;++i) dfs(h,i,0,pac);
//再去找atl
for(int j=0;j<n;++j) dfs(h,m-1,j,atl);
for(int i=0;i<m;++i) dfs(h,i,n-1,atl);
//然后根据两个标记数组，去记录下标
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
if(pac[i][j]&&atl[i][j])//如果坐标同时被两个数组标记了，就统计最终的结果
ret.push_back({i,j});
return ret;
}
void dfs(vector<vector<int>>& h,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&&!vis[x][y]&&h[x][y]>=h[i][j])
dfs(h,x,y,vis);
}
}
};六、扫雷游戏
. - 力扣（LeetCode）
class Solution {
public:
int dx[8]={0,0,1,-1,1,1,-1,-1};
int dy[8]={1,-1,0,0,1,-1,1,-1}; //周围的八个方向
int m,n;
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click)
{
m=board.size(),n=board[0].size();
//考虑边界情况，如果是雷，直接返回
int x=click[0],y=click[1];
if(board[x][y]=='M')
{
board[x][y]='X';
}
else//说明不是雷，dfs去判断该位置的情况
{
dfs(board,x,y);
}
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]='0'+count;
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);
}
}
}
};七、衣柜整理
. - 力扣（LeetCode）
class Solution {
public:
bool vis[100][100];
int m,n,cnt;
int ret;
int wardrobeFinishing(int _m, int _n, int _cnt)
{
m=_m,n=_n,cnt=_cnt;
ret=0;//统计符合要求的各自的数目
dfs(0,0);
return ret;
}
void dfs(int i,int j)
{
++ret;
vis[i][j]=true;
if(j+1<n&&check(i,j+1)&&!vis[i][j+1]) dfs(i,j+1);//向右找
if(i+1<m&&check(i+1,j)&&!vis[i+1][j]) dfs(i+1,j);//向下找
}
bool check(int i,int j)
{
int temp=0;
while(i)
{
temp+=(i%10);
i/=10;
}
while(j)
{
temp+=(j%10);
j/=10;
}
return temp<=cnt;
}
};
