• 岛屿问题（用DFS遍历二维数组）

    ​​​​​​一文秒杀所有岛屿题目 :: labuladong的算法小抄 (gitee.io)

    200. 岛屿数量 - 力扣（LeetCode）

    给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

    岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

    此外，你可以假设该网格的四条边均被水包围。

    示例 1：

    输入：grid = [
      ["1","1","1","1","0"],
      ["1","1","0","1","0"],
      ["1","1","0","0","0"],
      ["0","0","0","0","0"]
    ]
    输出：1

    思路：

    用DFS算法/BFS算法遍历二维数组，将二维矩阵中的每一个位置看做一个节点，这个节点的上下左右四个位置就是相邻节点，那么整个矩阵就可以抽象成一幅网状的图结构。因为是遍历一幅图，所以遍历的过程中还需要一个 visited 布尔数组防止走回头路。

    这道题中没有使用visited数组，而是选择每次遇到岛屿时，都用DFS算法把岛屿淹掉，避免了维护visited数组。

    1. class Solution {
    2. public:
    3.     int numIslands(vectorchar>>& grid) {
    4.         int res=0;
    5.         for(int i=0;isize();i++)
    6.         {
    7.             for(int j=0;j0].size();j++)
    8.             {
    9.                 if(grid[i][j]=='1')//grid[i][j]是陆地
    10.                 {
    11.                     dfs(i,j,grid);
    12.                     res++;
    13.                 }
    14.             }
    15.         }
    16.         return res;
    17.     }
    18.     //从grid[i][j]开始，把与之相邻的陆地都淹掉
    19.     void dfs(int i,int j,vectorchar>>& grid)
    20.     {
    21.         int m=grid.size();
    22.         int n=grid[0].size();
    23.         //处理越界
    24.         if(i<0||i>=m||j<0||j>=n)
    25.         {
    26.             return ;
    27.         }
    28.         if(grid[i][j]=='0')//已经是海水了
    29.         {
    30.             return ;
    31.         }
    32.         grid[i][j]='0';//把grid[i][j]淹掉
    33.         //把grid[i][j]的上下左右都淹掉
    34.         dfs(i-1,j,grid);
    35.         dfs(i+1,j,grid);
    36.         dfs(i,j-1,grid);
    37.         dfs(i,j+1,grid);
    38.     }
    39. };

    1254. 统计封闭岛屿的数目

    二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。

    请返回 封闭岛屿 的数目。

    示例 1：

    输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2
解释：
灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。

     思路：

    由题意得，靠边的陆地不算封闭岛屿，所以先用dfs把四条边上的陆地都排除掉，剩下的就是封闭岛屿。

    1. class Solution {
    2. public:
    3.     int closedIsland(vectorint>>& grid) {
    4.         int m=grid.size();
    5.         int n=grid[0].size();
    6.         int res=0;
    7.         //把边上的岛都淹掉
    8.         for(int i=0;i
    9.         {
    10.             dfs(grid,i,0);//把左边的岛都淹掉
    11.             dfs(grid,i,n-1);//把右边的岛都淹掉
    12.         }
    13.         for(int j=0;j
    14.         {
    15.             dfs(grid,0,j);//把上边的岛都淹掉
    16.             dfs(grid,m-1,j);//把下边的岛都淹掉
    17.         }
    18.         //遍历grid，此时剩下的岛屿都是封闭岛
    19.         for(int i=0;i
    20.         {
    21.             for(int j=0;j
    22.             {
    23.                 if(grid[i][j]==0)
    24.                 {
    25.                     res++;
    26.                     dfs(grid,i,j);
    27.                 }
    28.             }
    29.         }
    30.         return res;
    31.     }
    32.     //从grid[i][j]开始，把与之相邻的陆地都淹掉
    33.     void dfs(vectorint>>& grid,int i,int j)
    34.     {
    35.         int m=grid.size();
    36.         int n=grid[0].size();
    37.         //处理越界
    38.         if(i<0||j<0||i>=m||j>=n)
    39.         {
    40.             return ;
    41.         }
    42.         //已经是海水了
    43.         if(grid[i][j]==1)
    44.         {
    45.             return ;
    46.         }
    47.         //把grid[i][j]淹掉
    48.         grid[i][j]=1;
    49.         //把grid[i][j]的上下左右都淹掉
    50.         dfs(grid,i+1,j);
    51.         dfs(grid,i-1,j);
    52.         dfs(grid,i,j+1);
    53.         dfs(grid,i,j-1);
    54.     }
    55. };

    695. 岛屿的最大面积

    给你一个大小为 m x n 的二进制矩阵 grid 。

    岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

    岛屿的面积是岛上值为 1 的单元格的数目。

    计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

    示例 1：

    输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6

思路：
给dfs设置返回值，记录每次淹没的陆地的面积

    1. class Solution {
    2. public:
    3.     int maxAreaOfIsland(vectorint>>& grid) {
    4.         int res=0;
    5.         int m=grid.size();
    6.         int n=grid[0].size();
    7.         for(int i=0;i
    8.         {
    9.             for(int j=0;j
    10.             {
    11.                 if(grid[i][j]==1)
    12.                 {
    13.                     int cover=dfs(grid,i,j);
    14.                     res=max(cover,res);//选取面积最大的岛屿
    15.                 }
    16.             }
    17.         }
    18.         return res;
    19.     }
    20.     //淹没与grid[i][j]相邻的陆地，并返回淹没陆地的面积
    21.     int dfs(vectorint>>& grid,int i,int j)
    22.     {
    23.         int m=grid.size();
    24.         int n=grid[0].size();
    25.         if(i<0||j<0||i>=m||j>=n)
    26.         {
    27.             return 0;
    28.         }
    29.         if(grid[i][j]==0)
    30.         {
    31.             return 0;
    32.         }   
    33.         grid[i][j]=0;
    34.  
    35.         return dfs(grid,i+1,j)
    36.                 +dfs(grid,i-1,j)
    37.                 +dfs(grid,i,j+1)
    38.                 +dfs(grid,i,j-1)+1;
    39.     }
    40. };

    1905. 统计子岛屿 - 力扣（LeetCode）

    给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。

    如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。

    请你返回 grid2 中 子岛屿 的 数目 。

    示例 1：


    输入：grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
    输出：3
    解释：如上图所示，左边为 grid1 ，右边为 grid2 。
    grid2 中标红的 1 区域是子岛屿，总共有 3 个子岛屿。

    思路：

    如果岛屿2中存在一片陆地，在岛屿1的对应位置是海水，那么岛屿2就不是岛屿1的子岛 ，

    排除2中肯定不是子岛的岛屿

    现在2中剩下的肯定都是子岛，就可以计算子岛数量了

    1. class Solution {
    2. public:
    3.     int countSubIslands(vectorint>>& grid1, vectorint>>& grid2) {
    4.         int m=grid2.size();
    5.         int n=grid2[0].size();
    6.         //如果岛屿2中存在一片陆地，在岛屿1的对应位置是海水，那么岛屿2就不是岛屿1的子岛
    7.         for(int i=0;i
    8.         {
    9.             for(int j=0;j
    10.             {
    11.                 if(grid2[i][j]==1&&grid1[i][j]==0)//淹掉2中肯定不是子岛的岛屿
    12.                 {
    13.                     dfs(grid2,i,j);
    14.                 }
    15.             }
    16.         }
    17.         int res=0;
    18.         for(int i=0;i//现在2中剩下的肯定都是子岛，计算子岛数量
    19.         {
    20.             for(int j=0;j
    21.             {
    22.                 if(grid2[i][j]==1)
    23.                 {
    24.                     dfs(grid2,i,j);
    25.                     res++;
    26.                 }
    27.             }
    28.         }
    29.         return res;
    30.     }
    31.     void dfs(vectorint>>& grid2,int i,int j)
    32.     {
    33.         int m=grid2.size();
    34.         int n=grid2[0].size();
    35.         if(i<0||j<0||i>=m||j>=n)
    36.         {
    37.             return ;
    38.         }
    39.         if(grid2[i][j]==0)
    40.         {
    41.             return ;
    42.         }
    43.         grid2[i][j]=0;
    44.         dfs(grid2,i+1,j);
    45.         dfs(grid2,i-1,j);
    46.         dfs(grid2,i,j+1);
    47.         dfs(grid2,i,j-1);
    48.     }
    49. };

    827. 最大人工岛

    给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

    返回执行此操作后，grid 中最大的岛屿面积是多少？

    岛屿 由一组上、下、左、右四个方向相连的 1 形成。

    示例 1:

    输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。

    示例 2:

    输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。

    示例 3:

    输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。

     思路：

    1. 首先dfs找岛屿，找到一块就淹了它，并且给这个岛屿标记一下，存入HashMap（Key：岛屿的序号，Value，岛屿的面积）。给第一块岛屿标记为flag = -1，同时，在找的过程中，把访问到的格子的值改成flag。然后每当找到一块，flag--。有两个好处，第一，每块岛屿都被唯一标记了。第二，因为格子的值改成了小于0的flag，判断格子的值是否<=0就等效于visited数组的功能，使得回溯的过程中不会再访问已经访问过的格子。

    2. 对于已经标记完岛屿的地图，只需要挨个遍历，找到每个海洋（值为0）的格子，然后试一下上下左右是否可以连通，若联通，就计算一下联通之后的最大面积，更新答案。在这个过程中，需要用set判断上下左右有没有相同的岛屿，即每个岛屿只能加一次。

    3. 返回最大的答案

    例：grid={                         遍历之后----》                          grid={

                    {1,0,1},                                                                        {-1,0,-2},

                    {0,0,0},                                                                        {0,0,0},

                    {0,1,1}                                                                         {0,-3,-3}             

                    }                                                                                  }

    unoedered_map mapping={ ( -1 , 1 ),( -2 , 1 ),( -3 , 2 ) } 。

    1. class Solution {
    2. public:
    3.     int largestIsland(vectorint>>& grid) {
    4.         unordered_map<int,int> mapping;
    5.         int n=grid.size();
    6.         int flag=-1;//序号从-1开始递减，防止dfs时走回头路
    7.         for(int i=0;i//将grid中各个岛屿的面积都与序号flag联系起来
    8.         {
    9.             for(int j=0;j
    10.             {
    11.                 if(grid[i][j]==1)
    12.                 {
    13.                     int cover=dfs(grid,i,j,flag);
    14.                     mapping[flag]=cover;
    15.                     flag--;
    16.                 }
    17.             }
    18.         }
    19.         int res=0;
    20.         set<int> s;
    21.         for(int i=0;i
    22.         {
    23.             for(int j=0;j
    24.             {
    25.                 int cover=0;
    26.                 if(grid[i][j]==0)//假设将grid[i][j]变成陆地
    27.                 {
    28.                     int up=0,down=0,left=0,right=0;//记录grid[i][j]的上下左右情况
    29.                     if(i>0) up=grid[i-1][j];
    30.                     if(i-1) down=grid[i+1][j];
    31.                     if(j>0) left=grid[i][j-1];
    32.                     if(j-1) right=grid[i][j+1];
    33.                     //加入set中去重
    34.                     s.insert(up);
    35.                     s.insert(down);
    36.                     s.insert(left);
    37.                     s.insert(right);
    38.                     for(int dir:s)
    39.                     {
    40.                         if(dir<0)//小于0，那它就是一块陆地
    41.                         {
    42.                             cover+=mapping[dir];
    43.                         }
    44.                     }
    45.                     s.clear();//存完grid[i][j]的上下左右情况，记得要清空set
    46.                     cover++;//加上假设的那块陆地
    47.                 }
    48.                 res=max(res,cover);//求出最大面积
    49.             }
    50.         }
    51.         if(res==0)//如果grid全是陆地，那么最后res应该为n*n
    52.         {
    53.             res=n*n;
    54.         }
    55.         return res;
    56.     }
    57.  
    58.     int dfs(vectorint>>& grid,int i,int j,int flag)
    59.     {
    60.         int n=grid.size();
    61.         if(i>=n||j>=n||i<0||j<0)//超出边界，返回0
    62.             return 0;
    63.         if(grid[i][j]<=0)//如果是海水或者其他已经被淹掉的陆地，那么就返回0
    64.             return 0;
    65.         if(grid[i][j]==1)//如果是陆地，就用flag把它淹掉（用flag标记它）
    66.             grid[i][j]=flag;
    67.         return dfs(grid,i+1,j,flag)+
    68.                dfs(grid,i-1,j,flag)+
    69.                dfs(grid,i,j+1,flag)+
    70.                dfs(grid,i,j-1,flag)+1;
    71.     }
    72. };

    934. 最短的桥

    给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。

    岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。

    你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。

    返回必须翻转的 0 的最小数目。

    示例 1：

    输入：grid = [[0,1],[1,0]]
输出：1

    示例 2：

    输入：grid = [[0,1,0],[0,0,0],[0,0,1]]
输出：2

    示例 3：

    输入：grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
输出：1

    思路：

    最小翻转数 = 岛屿1 与 岛屿2 之间的最短路径
    dfs(遍历二维数组) + bfs(找到最短路径)
    如何找到最短路径？从一个岛屿开始，一圈一圈往外扩(BFS)，直到扩展到第二座岛 。

    遍历的思路类似于上题的最大人工岛，将遍历过的岛屿标记成“2”来做区分，而不是简单地淹掉。  

    1. class Solution {
    2. public:
    3.     int shortestBridge(vectorint>>& grid) {
    4.         vectorint>> dire={{1,0},{0,1},{-1,0},{0,-1}};
    5.         queueint,int>> q;//队列中装的是各点的坐标
    6.         int n=grid.size();
    7.         int count=1;
    8.         for(int i=0;i//只遍历一座岛屿，做队列的初始化
    9.         {
    10.             for(int j=0;j
    11.             {
    12.                 if(grid[i][j]==1&&count>0)
    13.                 {
    14.                     dfs(grid,q,i,j);
    15.                     count--;
    16.                 }
    17.             }
    18.         }
    19.         int step=0;
    20.         while(!q.empty())
    21.         {
    22.             int size=q.size();
    23.             for(int i=0;i//让岛屿周围的一圈海都向外扩展
    24.             {
    25.                 auto [x,y]=q.front();//用队头的pair赋给auto [x,y]，就不需要用first和second
    26.                 q.pop();
    27.                 if(grid[x][y]==1)//最终结果的条件判断
    28.                 {
    29.                     return step;
    30.                 }
    31.                 for(int j=0;jsize();j++)//从一个点向四个方向扩散(做选择)
    32.                 {
    33.                     int xn=x;
    34.                     int yn=y;
    35.                     xn+=dire[j][0];
    36.                     yn+=dire[j][1];
    37.                     if(xn<0||yn<0||xn>=n||yn>=n)
    38.                     {
    39.                         continue;    
    40.                     }
    41.                     if(grid[xn][yn]==0)//将周围的一圈海标记为2
    42.                     {
    43.                         grid[xn][yn]=2;
    44.                         q.emplace(xn,yn);
    45.                     }
    46.                     if(grid[xn][yn]==1)//扩散中接触到了陆地，最短路径为step+1
    47.                         return step+1;
    48.                 }
    49.             }
    50.             step++;
    51.         }
    52.         return -1;
    53.     }   
    54.     //深度优先遍历第一座岛，将岛屿及其周边的一圈都标记为 2
    55.     //将岛屿周边的一圈海的位置(i,j)压入队列中，做队列的初始化
    56.     void dfs(vectorint>>& grid,queueint,int>>& q,int i,int j)
    57.     {
    58.         int n=grid.size();
    59.         if(i<0||j<0||i>=n||j>=n)
    60.         {
    61.             return ;
    62.         }
    63.         if(grid[i][j]==0)//岛屿周边的一圈海
    64.         {
    65.             grid[i][j]=2;//标记为 2
    66.             q.emplace(i,j);//将其位置(i,j)压入队列中
    67.             return ;
    68.         }
    69.         if(grid[i][j]==2)//遇到已经遍历过的，直接返回
    70.             return ;
    71.         grid[i][j]=2;//将遍历到的岛屿标记为 2
    72.         dfs(grid,q,i+1,j);
    73.         dfs(grid,q,i,j+1);
    74.         dfs(grid,q,i-1,j);
    75.         dfs(grid,q,i,j-1);
    76.     }
    77. };
  • 相关阅读:
    HiEngine：可媲美本地的云原生内存数据库引擎
    ！力扣 108. 将有序数组转换为二叉搜索树
    mqant启动流程
    前端培训技术Less,Sass,Styus三者的区别
    此文带你详细了解MySQL数据库的存储引擎知识
    JAVA也能用上Seq啦
    微信小程序 java精品课程在线学习平台
    IPv6实现内网穿透，极低成本保姆级教程
    windows cmd 常用操作命令
    @Component 和 @Bean的区别
  • 原文地址：https://blog.csdn.net/weixin_50437588/article/details/126801063