devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

DFS 算法秒杀五道岛屿问题

作者：IT小白 | 2024-04-15 01:06:40

赞

踩

输入一个矩阵,0表示海洋,1表示陆地,将所有岛屿连成一个闭环

读完本文，可以去力扣解决如下题目：

200.岛屿数量（中等）

1254.统计封闭岛屿的数目（中等）

1020.飞地的数量（中等）

1905.统计子岛屿（中等）

694.不同的岛屿数量（中等）

ea5f446401a60a7ec742356efcec58b3.png

岛屿问题是经典的面试高频题，虽然基本的岛屿问题并不难，但是岛屿问题有一些有意思的扩展，比如求子岛屿数量，求形状不同的岛屿数量等等，本文就来把这些问题一网打尽。

岛屿系列问题的核心考点就是用 DFS/BFS 算法遍历二维数组。

本文主要来讲解如何用 DFS 算法来秒杀岛屿系列问题，不过用 BFS 算法的核心思路是完全一样的，无非就是把 DFS 改写成 BFS 而已。

那么如何在二维矩阵中使用 DFS 搜索呢？如果你把二维矩阵中的每一个位置看做一个节点，这个节点的上下左右四个位置就是相邻节点，那么整个矩阵就可以抽象成一幅网状的「图」结构。

根据学习数据结构和算法的框架思维，完全可以根据二叉树的遍历框架改写出二维矩阵的 DFS 代码框架：

  1. // 二叉树遍历框架
  2. void traverse(TreeNode root) {
  3.     traverse(root.left);
  4.     traverse(root.right);
  5. }
  6.  
  7. // 二维矩阵遍历框架
  8. void dfs(int[][] grid, int i, int j, boolean[] visited) {
  9.     int m = grid.length, n = grid[0].length;
  10.     if (i < 0 || j < 0 || i >= m || j >= n) {
  11.         // 超出索引边界
  12.         return;
  13.     }
  14.     if (visited[i][j]) {
  15.         // 已遍历过 (i, j)
  16.         return;
  17.     }
  18.     // 前序：进入节点 (i, j)
  19.     visited[i][j] = true;
  20.     dfs(grid, i - 1, j); // 上
  21.     dfs(grid, i + 1, j); // 下
  22.     dfs(grid, i, j - 1); // 左
  23.     dfs(grid, i, j + 1); // 右
  24.     // 后序：离开节点 (i, j)
  25.     // visited[i][j] = true;
  26. }

因为二维矩阵本质上是一幅「图」，所以遍历的过程中需要一个visited布尔数组防止走回头路，如果你能理解上面这段代码，那么搞定所有岛屿问题都很简单。

这里额外说一个处理二维数组的常用小技巧，你有时会看到使用「方向数组」来处理上下左右的遍历，和图遍历框架的代码很类似：

  1. // 方向数组，分别代表上、下、左、右
  2. int[][] dirs = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};
  3.  
  4. void dfs(int[][] grid, int i, int j, boolean[] visited) {
  5.     int m = grid.length, n = grid[0].length;
  6.     if (i < 0 || j < 0 || i >= m || j >= n) {
  7.         // 超出索引边界
  8.         return;
  9.     }
  10.     if (visited[i][j]) {
  11.         // 已遍历过 (i, j)
  12.         return;
  13.     }
  14.  
  15.     // 进入节点 (i, j)
  16.     visited[i][j] = true;
  17.     // 递归遍历上下左右的节点
  18.     for (int[] d : dirs) {
  19.         int next_i = i + d[0];
  20.         int next_j = j + d[1];
  21.         dfs(grid, next_i, next_j);
  22.     }
  23.     // 离开节点 (i, j)
  24.     // visited[i][j] = true;
  25. }

这种写法无非就是用 for 循环处理上下左右的遍历罢了，你可以按照个人喜好选择写法。

岛屿数量

这是力扣第 200 题「岛屿数量」，最简单也是最经典的一道岛屿问题，题目会输入一个二维数组grid，其中只包含0或者1，0代表海水，1代表陆地，且假设该矩阵四周都是被海水包围着的。

我们说连成片的陆地形成岛屿，那么请你写一个算法，计算这个矩阵grid中岛屿的个数，函数签名如下：

int numIslands(char[][] grid);

比如说题目给你输入下面这个grid有四片岛屿，算法应该返回 4：

af5d5f1aa635d741775ff397aabbad06.png

思路很简单，关键在于如何寻找并标记「岛屿」，这就要 DFS 算法发挥作用了，我们直接看解法代码：

  1. // 主函数，计算岛屿数量
  2. int numIslands(char[][] grid) {
  3.     int res = 0;
  4.     int m = grid.length, n = grid[0].length;
  5.     // 遍历 grid
  6.     for (int i = 0; i < m; i++) {
  7.         for (int j = 0; j < n; j++) {
  8.             if (grid[i][j] == '1') {
  9.                 // 每发现一个岛屿，岛屿数量加一
  10.                 res++;
  11.                 // 然后使用 DFS 将岛屿淹了
  12.                 dfs(grid, i, j);
  13.             }
  14.         }
  15.     }
  16.     return res;
  17. }
  18.  
  19. // 从 (i, j) 开始，将与之相邻的陆地都变成海水
  20. void dfs(char[][] grid, int i, int j) {
  21.     int m = grid.length, n = grid[0].length;
  22.     if (i < 0 || j < 0 || i >= m || j >= n) {
  23.         // 超出索引边界
  24.         return;
  25.     }
  26.     if (grid[i][j] == '0') {
  27.         // 已经是海水了
  28.         return;
  29.     }
  30.     // 将 (i, j) 变成海水
  31.     grid[i][j] = '0';
  32.     // 淹没上下左右的陆地
  33.     dfs(grid, i + 1, j);
  34.     dfs(grid, i, j + 1);
  35.     dfs(grid, i - 1, j);
  36.     dfs(grid, i, j - 1);
  37. }

为什么每次遇到岛屿，都要用 DFS 算法把岛屿「淹了」呢？主要是为了省事，避免维护visited数组。

因为dfs函数遍历到值为0的位置会直接返回，所以只要把经过的位置都设置为0，就可以起到不走回头路的作用。

PS：这类 DFS 算法还有个别名叫做 FloodFill 算法，现在有没有觉得 FloodFill 这个名字还挺贴切的~

这个最最基本的岛屿问题就说到这，我们来看看后面的题目有什么花样。

封闭岛屿的数量

上一题说二维矩阵四周可以认为也是被海水包围的，所以靠边的陆地也算作岛屿。

力扣第 1254 题「统计封闭岛屿的数目」和上一题有两点不同：

1、用0表示陆地，用1表示海水。

2、让你计算「封闭岛屿」的数目。所谓「封闭岛屿」就是上下左右全部被1包围的0，也就是说靠边的陆地不算作「封闭岛屿」。

函数签名如下：

int closedIsland(int[][] grid)

比如题目给你输入如下这个二维矩阵：

8a2469fcf14511e2de694c45cda5fe56.png

算法返回 2，只有图中灰色部分的0是四周全都被海水包围着的「封闭岛屿」。

那么如何判断「封闭岛屿」呢？其实很简单，把上一题中那些靠边的岛屿排除掉，剩下的不就是「封闭岛屿」了吗？

有了这个思路，就可以直接看代码了，注意这题规定0表示陆地，用1表示海水：

  1. // 主函数：计算封闭岛屿的数量
  2. int closedIsland(int[][] grid) {
  3.     int m = grid.length, n = grid[0].length;
  4.     for (int j = 0; j < n; j++) {
  5.         // 把靠上边的岛屿淹掉
  6.         dfs(grid, 0, j);
  7.         // 把靠下边的岛屿淹掉
  8.         dfs(grid, m - 1, j);
  9.     }
  10.     for (int i = 0; i < m; i++) {
  11.         // 把靠左边的岛屿淹掉
  12.         dfs(grid, i, 0);
  13.         // 把靠右边的岛屿淹掉
  14.         dfs(grid, i, n - 1);
  15.     }
  16.     // 遍历 grid，剩下的岛屿都是封闭岛屿
  17.     int res = 0;
  18.     for (int i = 0; i < m; i++) {
  19.         for (int j = 0; j < n; j++) {
  20.             if (grid[i][j] == 0) {
  21.                 res++;
  22.                 dfs(grid, i, j);
  23.             }
  24.         }
  25.     }
  26.     return res;
  27. }
  28.  
  29. // 从 (i, j) 开始，将与之相邻的陆地都变成海水
  30. void dfs(int[][] grid, int i, int j) {
  31.     int m = grid.length, n = grid[0].length;
  32.     if (i < 0 || j < 0 || i >= m || j >= n) {
  33.         return;
  34.     }
  35.     if (grid[i][j] == 1) {
  36.         // 已经是海水了
  37.         return;
  38.     }
  39.     // 将 (i, j) 变成海水
  40.     grid[i][j] = 1;
  41.     // 淹没上下左右的陆地
  42.     dfs(grid, i + 1, j);
  43.     dfs(grid, i, j + 1);
  44.     dfs(grid, i - 1, j);
  45.     dfs(grid, i, j - 1);
  46. }

只要提前把靠边的陆地都淹掉，然后算出来的就是封闭岛屿了。

PS：处理这类岛屿问题除了 DFS/BFS 算法之外，Union Find 并查集算法也是一种可选的方法。

这道岛屿题目的解法稍微改改就可以解决力扣第 1020 题「飞地的数量」，这题不让你求封闭岛屿的数量，而是求封闭岛屿的面积总和。

其实思路都是一样的，先把靠边的陆地淹掉，然后去数剩下的陆地数量就行了，注意第 1020 题中1代表陆地，0代表海水：

  1. int numEnclaves(int[][] grid) {
  2.     int m = grid.length, n = grid[0].length;
  3.     // 淹掉靠边的陆地
  4.     for (int i = 0; i < m; i++) {
  5.         dfs(grid, i, 0);
  6.         dfs(grid, i, n - 1);
  7.     }
  8.     for (int j = 0; j < n; j++) {
  9.         dfs(grid, 0, j);
  10.         dfs(grid, m - 1, j);
  11.     }
  12.  
  13.     // 数一数剩下的陆地
  14.     int res = 0;
  15.     for (int i = 0; i < m; i++) {
  16.         for (int j = 0; j < n; j++) {
  17.             if (grid[i][j] == 1) {
  18.                 res += 1;
  19.             }
  20.         }
  21.     }
  22.  
  23.     return res;
  24. }
  25.  
  26. // 和之前的实现类似
  27. void dfs(int[][] grid, int i, int j) {
  28.     // ...
  29. }

篇幅所限，具体代码我就不写了，我们继续看其他的岛屿问题。

岛屿的最大面积

这是力扣第 695 题「岛屿的最大面积」，0表示海水，1表示陆地，现在不让你计算岛屿的个数了，而是让你计算最大的那个岛屿的面积，函数签名如下：

int maxAreaOfIsland(int[][] grid)

比如题目给你输入如下一个二维矩阵：

2e3d98744f71d1bba1fb93a3bff8926c.png

其中面积最大的是橘红色的岛屿，算法返回它的面积 6。

这题的大体思路和之前完全一样，只不过dfs函数淹没岛屿的同时，还应该想办法记录这个岛屿的面积。

我们可以给dfs函数设置返回值，记录每次淹没的陆地的个数，直接看解法吧：

  1. int maxAreaOfIsland(int[][] grid) {
  2.     // 记录岛屿的最大面积
  3.     int res = 0;
  4.     int m = grid.length, n = grid[0].length;
  5.     for (int i = 0; i < m; i++) {
  6.         for (int j = 0; j < n; j++) {
  7.             if (grid[i][j] == 1) {
  8.                 // 淹没岛屿，并更新最大岛屿面积
  9.                 res = Math.max(res, dfs(grid, i, j));
  10.             }
  11.         }
  12.     }
  13.     return res;
  14. }
  15.  
  16. // 淹没与 (i, j) 相邻的陆地，并返回淹没的陆地面积
  17. int dfs(int[][] grid, int i, int j) {
  18.     int m = grid.length, n = grid[0].length;
  19.     if (i < 0 || j < 0 || i >= m || j >= n) {
  20.         // 超出索引边界
  21.         return 0;
  22.     }
  23.     if (grid[i][j] == 0) {
  24.         // 已经是海水了
  25.         return 0;
  26.     }
  27.     // 将 (i, j) 变成海水
  28.     grid[i][j] = 0;
  29.  
  30.     return dfs(grid, i + 1, j)
  31.          + dfs(grid, i, j + 1)
  32.          + dfs(grid, i - 1, j)
  33.          + dfs(grid, i, j - 1) + 1;
  34. }

解法和之前相比差不多，我也不多说了，接下来的两道岛屿问题是比较有技巧性的，我们重点来看一下。

子岛屿数量

如果说前面的题目都是模板题，那么力扣第 1905 题「统计子岛屿」可能得动动脑子了：

754c27af0e8a2c0877769c7a68bf6060.png

这道题的关键在于，如何快速判断子岛屿？肯定可以借助 Union Find 并查集 算法来判断，不过本文重点在 DFS 算法，就不展开并查集算法了。

什么情况下grid2中的一个岛屿B是grid1中的一个岛屿A的子岛？

当岛屿B中所有陆地在岛屿A中也是陆地的时候，岛屿B是岛屿A的子岛。

反过来说，如果岛屿B中存在一片陆地，在岛屿A的对应位置是海水，那么岛屿B就不是岛屿A的子岛。

那么，我们只要遍历grid2中的所有岛屿，把那些不可能是子岛的岛屿排除掉，剩下的就是子岛。

依据这个思路，可以直接写出下面的代码：

  1. int countSubIslands(int[][] grid1, int[][] grid2) {
  2.     int m = grid1.length, n = grid1[0].length;
  3.     for (int i = 0; i < m; i++) {
  4.         for (int j = 0; j < n; j++) {
  5.             if (grid1[i][j] == 0 && grid2[i][j] == 1) {
  6.                 // 这个岛屿肯定不是子岛，淹掉
  7.                 dfs(grid2, i, j);
  8.             }
  9.         }
  10.     }
  11.     // 现在 grid2 中剩下的岛屿都是子岛，计算岛屿数量
  12.     int res = 0;
  13.     for (int i = 0; i < m; i++) {
  14.         for (int j = 0; j < n; j++) {
  15.             if (grid2[i][j] == 1) {
  16.                 res++;
  17.                 dfs(grid2, i, j);
  18.             }
  19.         }
  20.     }
  21.     return res;
  22. }
  23.  
  24. // 从 (i, j) 开始，将与之相邻的陆地都变成海水
  25. void dfs(int[][] grid, int i, int j) {
  26.     int m = grid.length, n = grid[0].length;
  27.     if (i < 0 || j < 0 || i >= m || j >= n) {
  28.         return;
  29.     }
  30.     if (grid[i][j] == 0) {
  31.         return;
  32.     }
  33.  
  34.     grid[i][j] = 0;
  35.     dfs(grid, i + 1, j);
  36.     dfs(grid, i, j + 1);
  37.     dfs(grid, i - 1, j);
  38.     dfs(grid, i, j - 1);
  39. }

这道题的思路和计算「封闭岛屿」数量的思路有些类似，只不过后者排除那些靠边的岛屿，前者排除那些不可能是子岛的岛屿。

不同的岛屿数量

这是本文的最后一道岛屿题目，作为压轴题，当然是最有意思的。

力扣第 694 题「不同的岛屿数量」，题目还是输入一个二维矩阵，0表示海水，1表示陆地，这次让你计算 不同的 (distinct) 岛屿数量，函数签名如下：

int numDistinctIslands(int[][] grid)

比如题目输入下面这个二维矩阵：

86ee9524275895d26cab4e637a2059b8.png

其中有四个岛屿，但是左下角和右上角的岛屿形状相同，所以不同的岛屿共有三个，算法返回 3。

很显然我们得想办法把二维矩阵中的「岛屿」进行转化，变成比如字符串这样的类型，然后利用 HashSet 这样的数据结构去重，最终得到不同的岛屿的个数。

如果想把岛屿转化成字符串，说白了就是序列化，序列化说白了遍历嘛。

首先，对于形状相同的岛屿，如果从同一起点出发，dfs函数遍历的顺序肯定是一样的。

因为遍历顺序是写死在你的递归函数里面的，不会动态改变：

  1. void dfs(int[][] grid, int i, int j) {
  2.     // 递归顺序：
  3.     dfs(grid, i - 1, j); // 上
  4.     dfs(grid, i + 1, j); // 下
  5.     dfs(grid, i, j - 1); // 左
  6.     dfs(grid, i, j + 1); // 右
  7. }

所以，遍历顺序从某种意义上说就可以用来描述岛屿的形状，比如下图这两个岛屿：

d6564ca35e25e56e53fa71234a01e996.png

假设它们的遍历顺序是：

下，右，上，撤销上，撤销右，撤销下

如果我用分别用1, 2, 3, 4代表上下左右，用-1, -2, -3, -4代表上下左右的撤销，那么可以这样表示它们的遍历顺序：

2, 4, 1, -1, -4, -2

你看，这就相当于是岛屿序列化的结果，只要每次使用dfs遍历岛屿的时候生成这串数字进行比较，就可以计算到底有多少个不同的岛屿了。

要想生成这段数字，需要稍微改造dfs函数，添加一些函数参数以便记录遍历顺序：

  1. void dfs(int[][] grid, int i, int j, StringBuilder sb, int dir) {
  2.     int m = grid.length, n = grid[0].length;
  3.     if (i < 0 || j < 0 || i >= m || j >= n 
  4.         || grid[i][j] == 0) {
  5.         return;
  6.     }
  7.     // 前序遍历位置：进入 (i, j)
  8.     grid[i][j] = 0;
  9.     sb.append(dir).append(',');
  10.  
  11.     dfs(grid, i - 1, j, sb, 1); // 上
  12.     dfs(grid, i + 1, j, sb, 2); // 下
  13.     dfs(grid, i, j - 1, sb, 3); // 左
  14.     dfs(grid, i, j + 1, sb, 4); // 右
  15.  
  16.     // 后序遍历位置：离开 (i, j)
  17.     sb.append(-dir).append(',');
  18. }

dir记录方向，dfs函数递归结束后，sb记录着整个遍历顺序，其实这就是回溯算法框架，你看到头来这些算法都是相通的。

有了这个dfs函数就好办了，我们可以直接写出最后的解法代码：

  1. int numDistinctIslands(int[][] grid) {
  2.     int m = grid.length, n = grid[0].length;
  3.     // 记录所有岛屿的序列化结果
  4.     HashSet<String> islands = new HashSet<>();
  5.     for (int i = 0; i < m; i++) {
  6.         for (int j = 0; j < n; j++) {
  7.             if (grid[i][j] == 1) {
  8.                 // 淹掉这个岛屿，同时存储岛屿的序列化结果
  9.                 StringBuilder sb = new StringBuilder();
  10.                 // 初始的方向可以随便写，不影响正确性
  11.                 dfs(grid, i, j, sb, 666);
  12.                 islands.add(sb.toString());
  13.             }
  14.         }
  15.     }
  16.     // 不相同的岛屿数量
  17.     return islands.size();
  18. }

这样，这道题就解决了，至于为什么初始调用dfs函数时的dir参数可以随意写，这里涉及 DFS 和回溯算法的一个细微差别。

以上就是全部岛屿系列问题的解题思路，也许前面的题目大部分人会做，但是最后两题还是比较巧妙的，希望本文对你有帮助。 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/425021
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号