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
{
//先考虑边界条件，如果对应位置和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
{
//第一步，将当前位置修改成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 dfs(image,x,y,color); } } }; 二、岛屿问题 . - 力扣（LeetCode） class Solution { public: int ret=0; bool check[300][300]; int m,n; int numIslands(vector { m=grid.size(),n=grid[0].size(); for(int i=0;i for(int j=0;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 { //首先先把当前位置标记成选过 check[i][j]=true; //然后通过向量去其他位置找 for(int k=0;k<4;++k) { int x=i+dx[k],y=j+dy[k]; if(x>=0&&x 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 { m=grid.size(),n=grid[0].size(); int ret=0; for(int i=0;i for(int j=0;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 { ++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 { dfs(grid,x,y); } } } }; 四、被围绕的区域 . - 力扣（LeetCode） class Solution { public: //正难则反，先去找边界 //1先找到边界的o，然后用dfs去找 找到了就修改成. //2此时矩阵里的o肯定是在区域内的了，直接遍历一遍矩阵修改即可，顺便把.修改成圈 int m,n; void solve(vector { m=board.size(),n=board[0].size(); //先处理第一行的最后一行 for(int j=0;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 { 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 for(int j=0;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 { //先将当前位置改成. board[i][j]='.'; for(int k=0;k<4;++k) { int x=i+dx[k],y=j+dy[k]; if(x>=0&&x } } }; 五、太平洋大西洋水流问题 . - 力扣（LeetCode） class Solution { public: //思路，正难则反，用两个标记数组去标记两个大洋的位置 int m,n; vector int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; vector { m=h.size(),n=h[0].size(); //设置两个标记数组 vector auto atl=pac; //先去找pac for(int j=0;j for(int i=0;i //再去找atl for(int j=0;j for(int i=0;i //然后根据两个标记数组，去记录下标 for(int i=0;i for(int j=0;j if(pac[i][j]&&atl[i][j])//如果坐标同时被两个数组标记了，就统计最终的结果 ret.push_back({i,j}); return ret; } void dfs(vector { //先将该点设置为选过 vis[i][j]=true; //定义四个方向，然后去找 for(int k=0;k<4;++k) { int x=i+dx[k],y=j+dy[k]; if(x>=0&&x 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 { 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 { //进行搜索 int count=0;//用来数雷 for(int k=0;k<8;++k) { int x=i+dx[k],y=j+dy[k]; if(x>=0&&x } 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 } } } }; 七、衣柜整理 . - 力扣（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 if(i+1 } 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; } }; 好文阅读
发表评论