DFS：floodfill算法解决矩阵联通块问题

本文主要是介绍DFS：floodfill算法解决矩阵联通块问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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) //直接用引用，在矩阵上修改{//第一步，将当前位置修改成colorimage[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;//重置countdfs(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，然后.复原成Ofor(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;//先去找pacfor(int j=0;j<n;++j) dfs(h,0,j,pac);for(int i=0;i<m;++i) dfs(h,i,0,pac);//再去找atlfor(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;}
};