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

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

一.岛屿的数量

一.岛屿的数量

二.岛屿的周长

三. 岛屿的最大面积

四 统计封闭岛屿的数量

五.  飞地的数量

六  统计子岛屿的数量

对应letecode链接：

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

题目描述：

解题思路：

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

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

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

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

对应代码：

  1. class Solution {
  2. public:
  3.     int numIslands(vector<vector<char>>& grid) {
  4.                int ans=0;
  5.                for(int i=0;i<grid.size();i++){
  6.                    for(int j=0;j<grid[0].size();j++){
  7.                        if(grid[i][j]=='1'){//如果是1就递归去感染
  8.                            ans++;//数量加加
  9.                            infect(grid,i,j);
  10.                        }
  11.                    }
  12.                }
  13.                return ans;
  14.     }
  15.     void infect(vector<vector<char>>&board,int i,int j){
  16.         if(i<0||i==board.size()||j<0||j==board[0].size()||board[i][j]!='1'){
  17.             //越界直接返回或者不是字符一
  18.             return;
  19.         }
  20.         board[i][j]='0';//将其该为0
  21.         //向四个方向感染
  22.         infect(board,i-1,j);
  23.         infect(board,i+1,j);
  24.         infect(board,i,j-1);
  25.         infect(board,i,j+1);
  26.     }
  27. };

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

  1. class Solution {
  2. public:
  3.        vector<vector<bool>>visit;
  4.     int numIslands(vector<vector<char>>& grid) {
  5.           visit.resize(grid.size(),vector<bool>(grid[0].size()));
  6.                int ans=0;
  7.                for(int i=0;i<grid.size();i++){
  8.                    for(int j=0;j<grid[0].size();j++){
  9.                        if(grid[i][j]=='1'&&!visit[i][j]){//已经访问过了不要再访问了
  10.                     
  11.                            ans++;
  12.                            infect(grid,i,j);
  13.                        }
  14.                    }
  15.                }
  16.                return ans;
  17.     }
  18.     void infect(vector<vector<char>>&board,int i,int j){
  19.         if(i<0||i==board.size()||j<0||j==board[0].size()){//越界直接返回
  20.             return;
  21.         }
  22.         if(board[i][j]=='0'){
  23.             return;//不是字符1也直接返回
  24.         }
  25.         if(visit[i][j]){//已经访问过了直接返回
  26.             return;
  27.         }
  28.         visit[i][j]=true;//记录
  29.         //往四个方向感染
  30.         infect(board,i-1,j);
  31.         infect(board,i+1,j);
  32.         infect(board,i,j-1);
  33.         infect(board,i,j+1);
  34.     }
  35. };

二.岛屿的周长

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

题目描述：

解题思路：

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

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

对应代码：

  1. class Solution {
  2. public:
  3.     int islandPerimeter(vector<vector<int>>& grid) {
  4.           int m=grid.size();
  5.           int ans=0;
  6.           int n=grid[0].size();
  7.           for(int i=0;i<m;i++){
  8.               for(int j=0;j<n;j++){
  9.                   if(grid[i][j]==1){//如果为1直接记录感染记录答案
  10.                       ans+=infect(grid,i,j);
  11.                   }
  12.               }
  13.           }
  14.           return ans;
  15.     }
  16.     int infect(vector<vector<int>>&grid,int row ,int col){
  17.         if(row>=grid.size()||col>=grid[0].size()||row<0||col<0){//越界返回1说明是边界
  18.             return 1;
  19.         }
  20.         else if(grid[row][col]==2){//说明之前已经访问过了
  21.             return 0;
  22.         }
  23.         else if(grid[row][col]==0){//等于0返回
  24.             return 1;
  25.         }
  26.         else{
  27.             grid[row][col]=2;//说明是1将其改成2即可下次进来就不会重复计算
  28.          return   infect(grid,row+1,col)+//四个方向的结果累加
  29.             infect(grid,row-1,col)+
  30.             infect(grid,row,col-1)+
  31.             infect(grid,row,col+1);
  32.         }
  33.     }
  34.     
  35. };

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

  1. class Solution {
  2. public:
  3.       vector<vector<bool>>visit;//记录二维表中某个位置是否被访问
  4.     int islandPerimeter(vector<vector<int>>& grid) {
  5.           int m=grid.size();
  6.           int ans=0;
  7.           int n=grid[0].size();
  8.           visit.resize(m,vector<bool>(n));
  9.           for(int i=0;i<m;i++){
  10.               for(int j=0;j<n;j++){
  12.                   if(grid[i][j]==1&&!visit[i][j]){//如果已经被访问过了直接跳过
  13.                       ans+=infect(grid,i,j);
  14.                   }
  16.               }
  17.           }
  18.           return ans;
  19.     }
  20.     int infect(vector<vector<int>>&grid,int row ,int col){
  21.         if(row>=grid.size()||col>=grid[0].size()||row<0||col<0){//越界返回1说明是边界
  22.             return 1;
  23.         }
  24.         else if(visit[row][col]){//说明之前已经访问过了
  25.             return 0;
  26.         }
  27.         else if(grid[row][col]==0){//等于0返回
  28.             return 1;
  29.         }
  30.         else{
  31.            visit[row][col]=true;
  32.          return   infect(grid,row+1,col)+//四个方向的结果累加
  33.             infect(grid,row-1,col)+
  34.             infect(grid,row,col-1)+
  35.             infect(grid,row,col+1);
  36.         }
  37.     }
  38.     
  39. };

三. 岛屿的最大面积

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

题目描述：

解题思路：

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

对应代码：

  1. class Solution {
  2. public:
  3. vector<vector<bool>>visit;
  4.     int maxAreaOfIsland(vector<vector<int>>& grid) {
  5.         int ans=0;
  6.         visit.resize(grid.size(),vector<bool>(grid[0].size()));
  7.             for(int i=0;i<grid.size();i++){
  8.                 for(int j=0;j<grid[0].size();j++){
  9.                     if(grid[i][j]==1){//如果等于1就感染更新答案
  10.                       ans=max(dfs(grid,i,j),ans);
  11.                     }
  12.                 }
  13.             }
  14.             return ans;
  15.     }
  16.     int dfs(vector<vector<int>>&grid,int row,int col){
  17.              if(row<0||col<0||row>=grid.size()||col>=grid[0].size()||visit[row][col]){
  18.                  return 0;//visit[row][col]=true说明已经访问过了
  19.              }
  20.              else if(grid[row][col]==1){
  21.                 visit[row][col]=true;
  22.                  return 1+dfs(grid,row,col-1)+dfs(grid,row,col+1)//自己加上四个方向的数量
  23.                  +dfs(grid,row+1,col)+dfs(grid,row-1,col);
  24.              }
  25.              //说明它等于grid[row][col]=0直接返回0即可
  26.              return 0;
  27.     }
  28. };

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

  1. class Solution {
  2. public:
  3.     int maxAreaOfIsland(vector<vector<int>>& grid) {
  4.         int ans=0;
  5.             for(int i=0;i<grid.size();i++){
  6.                 for(int j=0;j<grid[0].size();j++){
  7.                     if(grid[i][j]==1){//等于1向四个方向感染并更新答案
  8.                       ans=max(dfs(grid,i,j),ans);
  9.                     }
  10.                 }
  11.             }
  12.             return ans;
  13.     }
  14.     int dfs(vector<vector<int>>&grid,int row,int col){
  15.              if(row<0||col<0||row>=grid.size()||col>=grid[0].size()){
  16.                  return 0;
  17.              }
  18.              else if(grid[row][col]==1){
  19.                  grid[row][col]=0;//访问过将其改为0；
  20.                  return 1+dfs(grid,row,col-1)+dfs(grid,row,col+1)//四个方向递归
  21.                  +dfs(grid,row+1,col)+dfs(grid,row-1,col);
  22.              }
  23.              //说明它等于grid[row][col]=0
  24.              return 0;
  25.     }
  26. };

四 统计封闭岛屿的数量

对应letecode链接：

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

题目描述：

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

对应代码：

  1. class Solution {
  2. public:
  3.           vector<vector<bool>>visit;//记录每个位置是否记录过
  4.     int closedIsland(vector<vector<int>>& grid) {
  5.              visit.resize(grid.size(),vector<bool>(grid[0].size()));
  6.              int ans=0;
  7.              for(int i=0;i<grid.size();i++){
  8.                  for(int j=0;j<grid[0].size();j++){
  9.                      if(grid[i][j]==0&&!visit[i][j]){
  10.                          if(!dfs(grid,i,j)){//如果返回的结果为false说明找到了
  11.                              ans++;
  12.                          }
  13.                      }
  14.                  }
  15.              }
  16.              return ans;
  17.     }
  18.     bool dfs(vector<vector<int>>&grid,int row,int col){
  19.         if(row<0||row>=grid.size()||col<0||col>=grid[0].size()){
  20.             return true;
  21.         }
  22.             if(grid[row][col]==1){
  23.                 return false;
  24.             }
  25.             if(visit[row][col]){//判断是否已经访问过了
  26.                 return false;
  27.             }
  28.             visit[row][col]=true;
  29.             //四个方向都要遍历不能只遍历一个方向
  30.             bool ret1= dfs(grid,row,col-1);//四个方向一点要遍历完毕才能停止
  31.             bool ret2=dfs(grid,row,col+1);
  32.             bool ret3=dfs(grid,row+1,col);
  33.             bool ret4=dfs(grid,row-1,col);
  34.     
  35.           return ret1||ret2||ret3||ret4;//四个方向只要一个为true就直接返回
  36.         
  37.     }
  38. };

五.  飞地的数量

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

题目描述：

解题思路：

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

对应代码：

  1. class Solution {
  2. public:
  3. vector<vector<bool>>visit;
  5.     int numEnclaves(vector<vector<int>>& grid) {
  6.          visit.resize(grid.size(),vector<bool>(grid[0].size()));
  7.        int m=grid.size();
  8.        int n=grid[0].size();
  9.     visit.resize(m,vector<bool>(n));//记录每个位置是否被访问过
  10.          int ret=0;
  11.          for(int i=0;i<m;i++){
  12.              for(int j=0;j<n;j++){
  13.                  //从边界开始感染
  14.                  if(!i||!j||i==m-1||j==n-1&&grid[i][j]&&!visit[i][j]){//如果是边界向四方感
  15.                      dfs(grid,i,j);
  16.                  }
  17.              }
  18.          }
  19.          
  20.          for(int i=0;i<grid.size();i++){
  21.              for(int j=0;j<grid[0].size();j++){
  22.                  if(grid[i][j]==1&&!visit[i][j]){//如果它是1并且没有被感染过
  23.                      ret++;
  24.                  }
  25.              }
  26.          }
  27.          return ret;
  28.     }
  29.     void dfs(vector<vector<int>>&grid,int row,int col){
  30.        
  31.         if(row>=0&&row<grid.size()&&col<grid[0].size()&&col>=0&&!visit[row][col]&&grid[row][col]!=0){
  32.               visit[row][col]=true;
  33.              dfs(grid,row,col-1);
  34.              dfs(grid,row,col+1);
  35.              dfs(grid,row+1,col);
  36.              dfs(grid,row-1,col);
  37.         }
  38.        
  39.        
  40.     }
  41. };

 六  统计子岛屿的数量

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

题目描述：

解题思路：

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

对应代码：

同样的给出两种版本：

  1. class Solution {
  2. public:
  3.           vector<vector<bool>>visit;
  4.     int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
  5.         int m = grid2.size(), n = grid2[0].size(), res = 0;
  6.               visit.resize(m,vector<bool>(n));
  7.         for (int row = 0; row < m; row++)
  8.             for (int col = 0; col < n; col++)
  9.                 if (grid2[row][col]&&!visit[row][col])//该点为1并且已经访问过了
  10.                     res += dfs(grid1, grid2, row, col);
  11.         return res;
  12.     }
  14. private:
  15.     bool dfs(vector<vector<int>>& grid1, vector<vector<int>>& grid2, int row, int col) {
  16.         if(row < 0 || col < 0 || row >= grid2.size() || col >= grid2[0].size() || 
  17.             !grid2[row][col]) return true;
  18.             if(visit[row][col])//访问过了之后直接返回
  19.             {
  20.                 return true;
  21.             }
  22.           visit[row][col]=true;//将其标记为true说明已经访问过了
  24.         return 
  25.             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) ;
  26.     }
  27. };

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

  1. class Solution {
  2. public:
  3.     int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
  4.         int m = grid2.size(), n = grid2[0].size(), res = 0;
  5.         for (int row = 0; row < m; row++)
  6.             for (int col = 0; col < n; col++)
  7.                 if (grid2[row][col])//如果是1
  8.                     res += dfs(grid1, grid2, row, col);
  9.         return res;
  10.     }
  12. private:
  13.     bool dfs(vector<vector<int>>& grid1, vector<vector<int>>& grid2, int row, int col) {
  14.         if(row < 0 || col < 0 || row >= grid2.size() || col >= grid2[0].size() || 
  15.             !grid2[row][col]) return true;
  16.         grid2[row][col] = 0; // 设置已经遍历过标志
  17.         //四个方向都遍历
  18.         return dfs(grid1, grid2, row + 1, col) & dfs(grid1, grid2, row - 1, col) &
  19.             dfs(grid1, grid2, row, col + 1) & dfs(grid1, grid2, row , col - 1) & 
  20.             grid1[row][col];
  21.     }
  22. };

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/qq_56999918/article/details/123674375

内容来源于网络，如有侵权，请联系作者删除！

c++

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com