AI summary
type
status
date
slug
summary
category
tags
icon
password
岛屿系列算法问题是经典的面试高频题，虽然基本的问题并不难，但是这类问题有一些有意思的扩展，比如求子岛屿数量，求形状不同的岛屿数量等等，本文就来把这些问题一网打尽。
岛屿系列题目的核心考点就是用 DFS/BFS 算法遍历二维数组。
本文主要来讲解如何用 DFS 算法来秒杀岛屿系列题目，不过用 BFS 算法的核心思路是完全一样的，无非就是把 DFS 改写成 BFS 而已。
那么如何在二维矩阵中使用 DFS 搜索呢？如果你把二维矩阵中的每一个位置看做一个节点，这个节点的上下左右四个位置就是相邻节点，那么整个矩阵就可以抽象成一幅网状的「图」结构。
完全可以根据二叉树的遍历框架改写出二维矩阵的 DFS 代码框架：
因为二维矩阵本质上是一幅「图」，所以遍历的过程中需要一个 visited 布尔数组防止走回头路，如果你能理解上面这段代码，那么搞定所有岛屿系列题目都很简单。
这里额外说一个处理二维数组的常用小技巧，你有时会看到使用「方向数组」来处理上下左右的遍历：
这种写法无非就是用 for 循环处理上下左右的遍历罢了，你可以按照个人喜好选择写法。下面就按照上述框架来解题。

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
最简单也是最经典的一道问题，思路很简单，关键在于如何寻找并标记「岛屿」，这就要 DFS 算法发挥作用了，我们直接看解法代码：
为什么每次遇到岛屿，都要用 DFS 算法把岛屿「淹了」呢？主要是为了省事，避免维护 visited 数组。
因为 dfs 函数遍历到值为 0 的位置会直接返回，所以只要把经过的位置都设置为 0，就可以起到不走回头路的作用。
这类 DFS 算法还有个别名叫做 FloodFill 算法，现在有没有觉得 FloodFill 这个名字还挺贴切的~
这个最最基本的算法问题就说到这，我们来看看后面的题目有什么花样。

1254. 统计封闭岛屿的数目

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。
请返回 封闭岛屿 的数目。
notion image
和上一题有两点不同：
  1. 用 0 表示陆地，用 1 表示海水。
  1. 让你计算「封闭岛屿」的数目。所谓「封闭岛屿」就是上下左右全部被 1 包围的 0，也就是说靠边的陆地不算作「封闭岛屿」。
那么如何判断「封闭岛屿」呢？其实很简单，把上一题中那些靠边的岛屿排除掉，剩下的不就是「封闭岛屿」了吗？
有了这个思路，就可以直接看代码了，注意这题规定 0 表示陆地，用 1 表示海水：
处理这类岛屿题目除了 DFS/BFS 算法之外，Union Find 并查集算法也是一种可选的方法，前文 Union-Find 并查集算法 就用 Union Find 算法解决了一道类似的问题。
另外，这道岛屿题目的解法稍微改改就可以解决力扣第 1020 题「飞地的数量」，这题不让你求封闭岛屿的数量，而是求封闭岛屿的面积总和。
其实思路都是一样的，先把靠边的陆地淹掉，然后去数剩下的陆地数量就行了，非常简单。不过注意第 1020 题中 1 代表陆地，0 代表海水。
篇幅所限，具体代码我就不写了，我们继续看其他的岛屿题目。

695. 岛屿的最大面积

0 表示海水，1 表示陆地，现在不让你计算岛屿的个数了，而是让你计算最大的那个岛屿的面积。
这题的大体思路和之前完全一样，只不过 dfs 函数淹没岛屿的同时，还应该想办法记录这个岛屿的面积。
我们可以给 dfs 函数设置返回值，记录每次淹没的陆地的个数，直接看解法吧：
解法和之前相比差不多，我也不多说了，接下来的两道岛屿题目是比较有技巧性的，我们重点来看一下。

1905. 统计子岛屿

给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。
如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。
请你返回 grid2 中 子岛屿 的 数目 。
什么情况下 grid2 中的一个岛屿 B 是 grid1 中的一个岛屿 A 的子岛？
当岛屿 B 中所有陆地在岛屿 A 中也是陆地的时候，岛屿 B 是岛屿 A 的子岛。
反过来说，如果岛屿 B 中存在一片陆地，在岛屿 A 的对应位置是海水，那么岛屿 B 就不是岛屿 A 的子岛。
那么，我们只要遍历 grid2 中的所有岛屿，把那些不可能是子岛的岛屿排除掉，剩下的就是子岛。
代码如下：
这道题的思路和计算「封闭岛屿」数量的思路有些类似，只不过后者排除那些靠边的岛屿，前者排除那些不可能是子岛的岛屿。

694. 不同岛屿的数量

题目还是输入一个二维矩阵，0 表示海水，1 表示陆地，这次让你计算 不同的 (distinct) 岛屿数量。
比如题目输入下面这个二维矩阵：
notion image
其中有四个岛屿，但是左下角和右上角的岛屿形状相同，所以不同的岛屿共有三个，算法返回 3。
很显然我们得想办法把二维矩阵中的「岛屿」进行转化，变成比如字符串这样的类型，然后利用 HashSet 这样的数据结构去重，最终得到不同的岛屿的个数。
如果想把岛屿转化成字符串，说白了就是序列化，序列化说白了就是遍历嘛，前文 二叉树的序列化和反序列化 讲了二叉树和字符串互转，这里也是类似的。
首先，对于形状相同的岛屿，如果从同一起点出发，dfs 函数遍历的顺序肯定是一样的。
因为遍历顺序是写死在你的递归函数里面的，不会动态改变。
所以，遍历顺序从某种意义上说就可以用来描述岛屿的形状，比如下图这两个岛屿：
notion image
如果我用分别用 1, 2, 3, 4 代表上下左右，用 -1, -2, -3, -4 代表上下左右的撤销，那么可以这样表示它们的遍历顺序：2, 4, 1, -1, -4, -2 。
你看，这就相当于是岛屿序列化的结果，只要每次使用 dfs 遍历岛屿的时候生成这串数字进行比较，就可以计算到底有多少个不同的岛屿了。
细心的读者问到，为什么记录「撤销」操作才能唯一表示遍历顺序呢？不记录撤销操作好像也可以？不对，实际上必须记录撤销操作。
比方说「下，右，撤销右，撤销下」和「下，撤销下，右，撤销右」显然是两个不同的遍历顺序，但如果不记录撤销操作，那么它俩都是「下，右」，成了相同的遍历顺序，显然是不对的。
另外，因为 for 循环是从左上到右下，所以相同岛屿的起点是固定的，所以得到的序列是相同的。
所以我们需要稍微改造 dfs 函数，添加一些函数参数以便记录遍历顺序：
仔细看这个代码，在递归前做选择，在递归后撤销选择，它像不像 回溯算法框架？实际上它就是回溯算法，因为它关注的是「树枝」（岛屿的遍历顺序），而不是「节点」（岛屿的每个格子）。
你完全可以把这个函数改写成回溯算法的标准形式。
dir 记录方向，dfs 函数递归结束后，sb 记录着整个遍历顺序。有了这个 dfs 函数就好办了，我们可以直接写出最后的解法代码：
这样，这道题就解决了，至于为什么初始调用 dfs 函数时的 dir 参数可以随意写，因为这个 dfs 函数实际上是回溯算法，它关注的是「树枝」而不是「节点」。
以上就是全部岛屿系列题目的解题思路，也许前面的题目大部分人会做，但是最后两题还是比较巧妙的，希望本文对你有帮助。