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) //直接用引用，在矩阵上修改
    {
       //第一步，将当前位置修改成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;
    }
};