一把王者的时间拿捏岛屿问题(dfs)

x33g5p2x  于2022-03-25 转载在 其他  
字(8.2k)|赞(0)|评价(0)|浏览(244)

一.岛屿的数量

一.岛屿的数量

二.岛屿的周长

三. 岛屿的最大面积

四 统计封闭岛屿的数量

五.  飞地的数量

六  统计子岛屿的数量

对应letecode链接:

200. 岛屿数量 - 力扣(LeetCode) (leetcode-cn.com)

题目描述:

解题思路:

我们首先明确一下岛屿问题中的网格结构是如何定义的,以方便我们后面的讨论。

网格问题是由 m ×n 个小方格组成一个网格,每个小方格与其上下左右四个方格认为是相邻的,要在这样的网格上进行某种搜索。

岛屿问题是一类典型的网格问题。每个格子中的数字可能是 0 或者 1。我们把数字为 0 的格子看成海洋格子,数字为 1 的格子看成陆地格子,这样相邻的陆地格子就连接成一个岛屿

我们只需要两个for循环遍历数组遇到1就开始感染递归他的四个方向如果遇到1就将其改为0,如果不是1直接返回如果开越界也返回即可.

对应代码:

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
               int ans=0;
               for(int i=0;i<grid.size();i++){
                   for(int j=0;j<grid[0].size();j++){
                       if(grid[i][j]=='1'){//如果是1就递归去感染
                           ans++;//数量加加
                           infect(grid,i,j);
                       }
                   }
               }
               return ans;
    }
    void infect(vector<vector<char>>&board,int i,int j){
        if(i<0||i==board.size()||j<0||j==board[0].size()||board[i][j]!='1'){
            //越界直接返回或者不是字符一
            return;
        }
        board[i][j]='0';//将其该为0
        //向四个方向感染
        infect(board,i-1,j);
        infect(board,i+1,j);
        infect(board,i,j-1);
        infect(board,i,j+1);
    }
};

不过了这样修该了原来的数组,博主感觉不太好感觉太挫了,博主给出另外一种解法:定义一个二维数组记录访问过的位置即可。下面给出代码:

class Solution {
public:
       vector<vector<bool>>visit;
    int numIslands(vector<vector<char>>& grid) {
          visit.resize(grid.size(),vector<bool>(grid[0].size()));
               int ans=0;
               for(int i=0;i<grid.size();i++){
                   for(int j=0;j<grid[0].size();j++){
                       if(grid[i][j]=='1'&&!visit[i][j]){//已经访问过了不要再访问了
                    
                           ans++;
                           infect(grid,i,j);
                       }
                   }
               }
               return ans;
    }
    void infect(vector<vector<char>>&board,int i,int j){
        if(i<0||i==board.size()||j<0||j==board[0].size()){//越界直接返回
            return;
        }
        if(board[i][j]=='0'){
            return;//不是字符1也直接返回
        }
        if(visit[i][j]){//已经访问过了直接返回
            return;
        }
        visit[i][j]=true;//记录
        //往四个方向感染
        infect(board,i-1,j);
        infect(board,i+1,j);
        infect(board,i,j-1);
        infect(board,i,j+1);
    }
};

二.岛屿的周长

463. 岛屿的周长 - 力扣(LeetCode) (leetcode-cn.com)

题目描述:

解题思路:

本题思路和上题基本差不多,只不过本题如果到达边界我们需要返回1,这是因为如果越界了说明找到了周长之中的一条边。同样的我们需要将递归途中遇到的1全部改为其他数字否则递归将无法停止

在这里我们选择将其改为2.:

对应代码:

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
          int m=grid.size();
          int ans=0;
          int n=grid[0].size();
          for(int i=0;i<m;i++){
              for(int j=0;j<n;j++){
                  if(grid[i][j]==1){//如果为1直接记录感染记录答案
                      ans+=infect(grid,i,j);
                  }
              }
          }
          return ans;
    }
    int infect(vector<vector<int>>&grid,int row ,int col){
        if(row>=grid.size()||col>=grid[0].size()||row<0||col<0){//越界返回1说明是边界
            return 1;
        }
        else if(grid[row][col]==2){//说明之前已经访问过了
            return 0;
        }
        else if(grid[row][col]==0){//等于0返回
            return 1;
        }
        else{
            grid[row][col]=2;//说明是1将其改成2即可下次进来就不会重复计算
         return   infect(grid,row+1,col)+//四个方向的结果累加
            infect(grid,row-1,col)+
            infect(grid,row,col-1)+
            infect(grid,row,col+1);
        }
    }
    
};

同样的如果不想修改数组,我们可以定义一个二维数组记录访问过的位置:

class Solution {
public:
      vector<vector<bool>>visit;//记录二维表中某个位置是否被访问
    int islandPerimeter(vector<vector<int>>& grid) {
          int m=grid.size();
          int ans=0;
          int n=grid[0].size();
          visit.resize(m,vector<bool>(n));
          for(int i=0;i<m;i++){
              for(int j=0;j<n;j++){

                  if(grid[i][j]==1&&!visit[i][j]){//如果已经被访问过了直接跳过
                      ans+=infect(grid,i,j);
                  }

              }
          }
          return ans;
    }
    int infect(vector<vector<int>>&grid,int row ,int col){
        if(row>=grid.size()||col>=grid[0].size()||row<0||col<0){//越界返回1说明是边界
            return 1;
        }
        else if(visit[row][col]){//说明之前已经访问过了
            return 0;
        }
        else if(grid[row][col]==0){//等于0返回
            return 1;
        }
        else{
           visit[row][col]=true;
         return   infect(grid,row+1,col)+//四个方向的结果累加
            infect(grid,row-1,col)+
            infect(grid,row,col-1)+
            infect(grid,row,col+1);
        }
    }
    
};

三. 岛屿的最大面积

剑指 Offer II 105. 岛屿的最大面积 - 力扣(LeetCode) (leetcode-cn.com)

题目描述:

解题思路:

本题思路和上题基本一模一样,上题是ans+=这个题只需要和返回值做比较即可。

对应代码:

class Solution {
public:
vector<vector<bool>>visit;
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans=0;
        visit.resize(grid.size(),vector<bool>(grid[0].size()));
            for(int i=0;i<grid.size();i++){
                for(int j=0;j<grid[0].size();j++){
                    if(grid[i][j]==1){//如果等于1就感染更新答案
                      ans=max(dfs(grid,i,j),ans);
                    }
                }
            }
            return ans;
    }
    int dfs(vector<vector<int>>&grid,int row,int col){
             if(row<0||col<0||row>=grid.size()||col>=grid[0].size()||visit[row][col]){
                 return 0;//visit[row][col]=true说明已经访问过了
             }
             else if(grid[row][col]==1){
                visit[row][col]=true;
                 return 1+dfs(grid,row,col-1)+dfs(grid,row,col+1)//自己加上四个方向的数量
                 +dfs(grid,row+1,col)+dfs(grid,row-1,col);
             }
             //说明它等于grid[row][col]=0直接返回0即可
             return 0;
    }
};

同样的给出两种方式一种使用一个二维数组记录位置,第二种方式是改变原数组中的值。

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans=0;
            for(int i=0;i<grid.size();i++){
                for(int j=0;j<grid[0].size();j++){
                    if(grid[i][j]==1){//等于1向四个方向感染并更新答案
                      ans=max(dfs(grid,i,j),ans);
                    }
                }
            }
            return ans;
    }
    int dfs(vector<vector<int>>&grid,int row,int col){
             if(row<0||col<0||row>=grid.size()||col>=grid[0].size()){
                 return 0;
             }
             else if(grid[row][col]==1){
                 grid[row][col]=0;//访问过将其改为0;
                 return 1+dfs(grid,row,col-1)+dfs(grid,row,col+1)//四个方向递归
                 +dfs(grid,row+1,col)+dfs(grid,row-1,col);
             }
             //说明它等于grid[row][col]=0
             return 0;
    }
};

四 统计封闭岛屿的数量

对应letecode链接:

1254. 统计封闭岛屿的数目 - 力扣(LeetCode) (leetcode-cn.com)

题目描述:

本题和上题思路不能说是相似真的是一模一样。思路都是如果一个位置为1向四个方向递归。

对应代码:

class Solution {
public:
          vector<vector<bool>>visit;//记录每个位置是否记录过
    int closedIsland(vector<vector<int>>& grid) {
             visit.resize(grid.size(),vector<bool>(grid[0].size()));
             int ans=0;
             for(int i=0;i<grid.size();i++){
                 for(int j=0;j<grid[0].size();j++){
                     if(grid[i][j]==0&&!visit[i][j]){
                         if(!dfs(grid,i,j)){//如果返回的结果为false说明找到了
                             ans++;
                         }
                     }
                 }
             }
             return ans;
    }
    bool dfs(vector<vector<int>>&grid,int row,int col){
        if(row<0||row>=grid.size()||col<0||col>=grid[0].size()){
            return true;
        }
            if(grid[row][col]==1){
                return false;
            }
            if(visit[row][col]){//判断是否已经访问过了
                return false;
            }
            visit[row][col]=true;
            //四个方向都要遍历不能只遍历一个方向
            bool ret1= dfs(grid,row,col-1);//四个方向一点要遍历完毕才能停止
            bool ret2=dfs(grid,row,col+1);
            bool ret3=dfs(grid,row+1,col);
            bool ret4=dfs(grid,row-1,col);
    
          return ret1||ret2||ret3||ret4;//四个方向只要一个为true就直接返回
        
    }
};

五.  飞地的数量

1020. 飞地的数量 - 力扣(LeetCode) (leetcode-cn.com)

题目描述:

解题思路:

本题等价于找到不和边缘相连的独立块的面积和,套用上题的模板即可。具体请看代码

对应代码:

class Solution {
public:
vector<vector<bool>>visit;

    int numEnclaves(vector<vector<int>>& grid) {
         visit.resize(grid.size(),vector<bool>(grid[0].size()));
       int m=grid.size();
       int n=grid[0].size();
    visit.resize(m,vector<bool>(n));//记录每个位置是否被访问过
         int ret=0;
         for(int i=0;i<m;i++){
             for(int j=0;j<n;j++){
                 //从边界开始感染
                 if(!i||!j||i==m-1||j==n-1&&grid[i][j]&&!visit[i][j]){//如果是边界向四方感
                     dfs(grid,i,j);
                 }
             }
         }
         
         for(int i=0;i<grid.size();i++){
             for(int j=0;j<grid[0].size();j++){
                 if(grid[i][j]==1&&!visit[i][j]){//如果它是1并且没有被感染过
                     ret++;
                 }
             }
         }
         return ret;
    }
    void dfs(vector<vector<int>>&grid,int row,int col){
       
        if(row>=0&&row<grid.size()&&col<grid[0].size()&&col>=0&&!visit[row][col]&&grid[row][col]!=0){
              visit[row][col]=true;
             dfs(grid,row,col-1);
             dfs(grid,row,col+1);
             dfs(grid,row+1,col);
             dfs(grid,row-1,col);
        }
       
       
    }
};

 六  统计子岛屿的数量

1905. 统计子岛屿 - 力扣(LeetCode) (leetcode-cn.com)

题目描述:

解题思路:

这道题稍微复杂了一点,增加了一个判断条件,其实就是要求对grid2的一次dfs中所有遍历到的为1的地方在grid1中同样为1。可以将这道题看做是 岛屿数量的类似题目

对应代码:

同样的给出两种版本:

class Solution {
public:
          vector<vector<bool>>visit;
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int m = grid2.size(), n = grid2[0].size(), res = 0;
              visit.resize(m,vector<bool>(n));
        for (int row = 0; row < m; row++)
            for (int col = 0; col < n; col++)
                if (grid2[row][col]&&!visit[row][col])//该点为1并且已经访问过了
                    res += dfs(grid1, grid2, row, col);
        return res;
    }

private:
    bool dfs(vector<vector<int>>& grid1, vector<vector<int>>& grid2, int row, int col) {
        if(row < 0 || col < 0 || row >= grid2.size() || col >= grid2[0].size() || 
            !grid2[row][col]) return true;
            if(visit[row][col])//访问过了之后直接返回
            {
                return true;
            }
          visit[row][col]=true;//将其标记为true说明已经访问过了

        return 
            grid1[row][col]&dfs(grid1, grid2, row + 1, col) & dfs(grid1, grid2, row - 1, col) &dfs(grid1, grid2, row, col + 1) & dfs(grid1, grid2, row , col - 1) ;
    }
};

方法二:修改原数组中的值:

class Solution {
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int m = grid2.size(), n = grid2[0].size(), res = 0;
        for (int row = 0; row < m; row++)
            for (int col = 0; col < n; col++)
                if (grid2[row][col])//如果是1
                    res += dfs(grid1, grid2, row, col);
        return res;
    }

private:
    bool dfs(vector<vector<int>>& grid1, vector<vector<int>>& grid2, int row, int col) {
        if(row < 0 || col < 0 || row >= grid2.size() || col >= grid2[0].size() || 
            !grid2[row][col]) return true;
        grid2[row][col] = 0; // 设置已经遍历过标志
        //四个方向都遍历
        return dfs(grid1, grid2, row + 1, col) & dfs(grid1, grid2, row - 1, col) &
            dfs(grid1, grid2, row, col + 1) & dfs(grid1, grid2, row , col - 1) & 
            grid1[row][col];
    }
};

相关文章