【甘泉算法】一文搞定“岛屿类”问题
leetcode上有许多非常有意思的题目，“岛屿类”问题绝对算得上有意思的题目，这些题目解决起来可能有点棘手，但是如果可以独立思考解决它，还是很锻炼人的思维能力的。其实这类“岛屿类”问题就是DFS（深度优先搜索）的应用，本文将结合leetcode上几道经典的题目，和大家一起来讨论讨论。
一、例题列表
这里列出本文需要解决的几道题，如下所示：
序号 | 题目 | 难度 |
|---|---|---|
1 | No.200 岛屿数量 | 中等 |
2 | No.462 岛屿的周长 | 简单 |
3 | No.695 岛屿的最大面积 | 中等 |
4 | No.827 最大人工岛 | 难 |
这几道题是DFS（深度优先遍历）的应用题，我们做的比较多的是将DFS应用到二叉树上，在二叉树上进行深度优先搜索，这也是我们熟知的DFS应用的方式，但是上面的四道题，基本都是类似于在二维网格进行深度优先遍历，那么这种深度优先搜索的方式是如何应用的呢？读者暂时不要着急，我们一起看下面的四道例题的详解，就知道深度优先搜索是是如何应用到了类似于二维网格中的。
二、框架分析
在讨论例题之前，我们一起来先看下上面的四道题的描述，看描述，基本可以得出网格的基本定义。网格是由一个m x n的格子组成，格子中的数字1表示陆地，0表示海洋，网格在题目中的表示方式是一个二维数组，由1连接起来的（上下左右，不含对角线）组成陆地，由0连接起来的构成海洋，如下所示：
上图中可以清晰地看出，网格中有三个岛屿，基于这种网格背景下，产生了如下几种题型：求岛屿数量，求岛屿面积、求岛屿周长，求最大岛屿面积等，这几种题型都可以使用DFS来解决。对于我们，比较熟知的是二叉树的DFS，它只需要按深度依次遍历左右子树即可，那么对于网格这种的DFS，它所需要遍历的是某个网格的上下左右四个格子，当然它们之间不仅仅这一点区别，我们一起对比下DFS的三个基本元素：递归终止条件、本层要做的事情、递归。
- 递归终止条件：二叉树做DFS的时候，终止条件一般都是遍历到无法再继续遍历为止，这个时候触发终止条件，然后返回；那么这个特性类比到网格上，那么一般都是遍历到了网格的边缘，然后返回；
- 本层要做的事情：这一点它们应该是一样的，本层要做的事情根据自身业务要求来确定即可；
- 递归：二叉树要分别递归到左子树和右子树，而网格要分别递归某个格子的上下左右四个格子。
二叉树的DFS的基本框架如下：
void traverse(TreeNode root) {
// 1.终止条件
if (root == null) {
return;
}
// 2.做本层需要做的事情，如读取节点的值等
// 3.递归
traverse(root.left);
traverse(root.left);
}对于网格，我们也可以类比写出网格的DFS框架，在写之前，我们一起来一步一步分析下，以帮助读者真正地理解框架是如何总结出来的。
递归终止条件
二叉树的终止条件是root == null，如果满足这个条件，说明已经不能再继续往下再遍历了，root都为null了，root.left和root.right都不能再继续访问了，否则会发生空指针异常。那么对于网格，当然也只能在网格内部进行遍历，不能超出网格的范围。我们定义某个格子的坐标为(r, c)，那么它上下左右四个格子的坐标分别为：(r - 1, c)、(r + 1, c)、(r, c - 1)、(r, c + 1)，如下所示：
当在遍历过程中，如果遍历到了网格外，那么说明就触发了终止条件，如下图所示：
分析了网格遍历的终止条件，那么其实就可以很容易得到它的终止条件的具体判断方式，那就是需要正在遍历的格子的坐标，看看坐标是否在网格内部，如果不在网格内部，那么就立即返回。具体的代码如下所示：
// 触发终止条件：判断当前遍历的格子是否在网格内
if (!isInGrid(grid, r, c)) {
return;
}网格一般都是由一个二维数组来表示，如：int[][] grid，那么判断坐标是否在网格内，代码就简单了，如下所示：
/**
* 判断指定坐标是否在网格内
*
* @param grid 表示网格的二维数组
* @param r 行坐标
* @param c 列坐标
* @return 是否在网格内
*/
private boolean isInGrid(char[][] grid, int r, int c) {
return r >= 0 && r < grid.length
&& c >= 0 && c < grid[0].length;
}本层要做的事情
二叉树在DFS的时候，遍历到某个层次，那么通常是读取该节点的值，用于正常逻辑处理。而这种网格类型的遍历，通常遍历到某个格子后，对格子进行标记，表明已经遍历过了，这种标记方式很多，但通常的处理方法都是将网格的值修改为固定的值，当下次再次遍历到这个格子的时候，如果发现格子已经遍历过了，那么就直接返回。这种以固定值的标记方式，还能防止格子被重复遍历，从而避免了重复值。
那么应用标记方式，本层处理的内容如下代码所示：
// 如果格子不是岛屿，那么直接返回，相当于剪枝，防止重复操作
if (grid[r][c] != '1') {
return;
}
// 做标记，将本层遍历后的格子标记为2
grid[r][c] = '2';递归
上面的终止条件和本层要做的事情都确定下来之后，递归就简单了，那么就是分别遍历该格子的上下左右四个格子，这里直接给出代码，如下所示：
// 递归访问上、下、左、右四个相邻格子
traverse(grid, r - 1, c);
traverse(grid, r + 1, c);
traverse(grid, r, c - 1);
traverse(grid, r, c + 1);综上所述，我们将这种网格类型的通用解题框架总结如下所示：
/**
* DFS
*
* @param grid 网格
* @param r 行坐标
* @param c 列坐标
*/
private void traverse(char[][] grid, int r, int c) {
// 触发终止条件：判断当前遍历的格子是否在网格内
if (!isInGrid(grid, r, c)) {
return;
}
// 本层要做的事情
// 如果格子不是岛屿，那么直接返回，相当于剪枝，防止重复操作
if (grid[r][c] != '1') {
return;
}
// 做标记，将本层遍历后的格子标记为2
grid[r][c] = '2';
// 递归访问上、下、左、右四个相邻格子
traverse(grid, r - 1, c);
traverse(grid, r + 1, c);
traverse(grid, r, c - 1);
traverse(grid, r, c + 1);
}
/**
* 判断指定坐标是否在网格内
*
* @param grid 表示网格的二维数组
* @param r 行坐标
* @param c 列坐标
* @return 是否在网格内
*/
private boolean isInGrid(char[][] grid, int r, int c) {
return r >= 0 && r < grid.length
&& c >= 0 && c < grid[0].length;
}有了这个框架，那么接下来的四道岛屿类型的网格题目，我们解决起来就轻松很多，请读者接着往下读，看看我们的兵器是否称手。
三、例题详解
3.1 岛屿数量
No.200 岛屿数量 这道题是一道经典的DFS的应用题，当然你也许还不明白我为何说它是一道DFS的应用题，那么就跟随我的节奏，看看我是如何应用DFS来解决这道题的，题目描述如下所示：
这道题其实不用我们过多讨论，其实在第二节中，我们一起讨论的网格类型的DFS就是按照这道题来进行分析的，我们这里直接粘出代码，读者一读既懂，代码如下所示：
/**
* DFS解决岛屿数量问题
*
* @param grid 二维数组
* @return 岛屿数量
*/
public int numIslands(char[][] grid) {
// 定义结果
int result = 0;
// 循环遍历
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == '1') {
dfs(grid, r, c);
result++;
}
}
}
return result;
}
/**
* DFS
*
* @param grid 网格
* @param r 行坐标
* @param c 列坐标
*/
private void dfs(char[][] grid, int r, int c) {
// 触发终止条件：判断当前遍历的格子是否在网格内
if (!isInGrid(grid, r, c)) {
return;
}
// 本层要做的事情
// 如果格子不是岛屿，那么直接返回，相当于剪枝，防止重复操作
if (grid[r][c] != '1') {
return;
}
// 做标记，将本层遍历后的格子标记为-1
grid[r][c] = '2';
// 递归访问上、下、左、右四个相邻格子
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
/**
* 判断指定坐标是否在网格内
*
* @param grid 表示网格的二维数组
* @param r 行坐标
* @param c 列坐标
* @return 是否在网格内
*/
private boolean isInGrid(char[][] grid, int r, int c) {
return r >= 0 && r < grid.length
&& c >= 0 && c < grid[0].length;
}代码是不是很简单？我们总结了套路，那么直接按照讨论来出牌，基本就可以成功解决这类问题，我们继续看后面的三道题。
3.2 岛屿的周长
本题选择leetcode第463题：岛屿的周长，leetcode将其标记为简单题，其实难度和上面一题差不多，甚至说是细节这一块可能还没有上一题那么好想到。我们一起看下面的题目要求。
题目要求就是求取一个岛屿的周长，我们都知道，一个网格有四条边，那么哪些边该计入到周长中呢？假设我们已经遍历到了一个陆地网格，那么我们需要递归遍历该网格上下左右四个方向相邻网格，直到所有相连的陆地网格都遍历完毕。对于某个正在遍历的网格，存在下面三种情况：
- 如果该网格是海洋，那么周长就加1，对应上图中网格与海洋接壤的边；
- 如果遍历的网格超出了范围，那么周长也加1，对应上图中网格的边界；
- 如果遍历的网格是已经遍历过的陆地，那么周长不加任何值，因为这条边是陆地网格与陆地网格的接壤，不能算到周长里面。
有了上面的理论分析，代码写起来就很简单了，也是套用框架即可，代码如下：
/**
* DFS解决岛屿周长问题
*
* @param grid 二维数组
* @return 岛屿周长
*/
public int islandPerimeter(int[][] grid) {
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == 1) {
// 本题只有一个岛屿，所以遍历到岛屿后就直接返回即可
return dfs(grid, r, c);
}
}
}
return 0;
}
/**
* DFS
*
* @param grid 网格
* @param r 行坐标
* @param c 列坐标
* @return 岛屿周长
*/
private int dfs(int[][] grid, int r, int c) {
// 终止条件
if (!isInGrid(grid, r, c)) {
// 说明遍历到了边界，那么直接返回边界的一条边
return 1;
}
if (grid[r][c] == 0) {
// 说明遍历到了海洋，返回一条与海洋接壤的一条边
return 1;
}
if (grid[r][c] == 2) {
// 说明已经遍历过，是陆地接壤处，不能算到周长里面
return 0;
}
// 本层要做的事情，将遍历过的陆地网格设置为2
grid[r][c] = 2;
// 递归遍历，上下左右
return dfs(grid, r - 1, c) + dfs(grid, r + 1, c) + dfs(grid, r, c - 1) + dfs(grid, r, c + 1);
}
/**
* 判断指定坐标是否在网格内
*
* @param grid 表示网格的二维数组
* @param r 行坐标
* @param c 列坐标
* @return 是否在网格内
*/
private boolean isInGrid(int[][] grid, int r, int c) {
return r >= 0 && r < grid.length
&& c >= 0 && c < grid[0].length;
}3.3 岛屿的最大面积
本道题选自leetcode第695题：岛屿的最大面积，有了前面两道题的铺垫，相信读者很快就有解决这道题的思路。
我们遍历网格，当遍历到某个陆地网格的时候，深度遍历该网格上下左右四个网格，对于某个网格，如果是陆地（值为1），那么我们的面积就加1，且将遍历过的陆地网格标记为2，然后按照DFS的遍历方式，将一个岛屿的面积累加起来，再去继续遍历其他岛屿，直到遍历完所有的岛屿，这个时候，最大岛屿的面积也就求取出来了。
这里直接给出代码：
/**
* DFS求取最大岛屿面积
*
* @param grid 网格
* @return 最大面积
*/
public int maxAreaOfIsland(int[][] grid) {
// 定义结果集
int result = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == 1) {
int area = dfs(grid, r, c);
result = Math.max(result, area);
}
}
}
return result;
}
/**
* DFS求取岛屿面积
*
* @param grid 网格
* @param r 行坐标
* @param c 列坐标
* @return 面积
*/
private int dfs(int[][] grid, int r, int c) {
// 终止条件：遍历到网格外，遍历到海洋或者已经遍历过都直接返回0
if (!isInGrid(grid, r, c) || grid[r][c] != 1) {
return 0;
}
// 做本层要做的事情
// 遍历过的陆地部分标记为2
grid[r][c] = 2;
// 递归访问上、下、左、右四个相邻格子
return 1 + dfs(grid, r - 1, c) + dfs(grid, r + 1, c) + dfs(grid, r, c - 1) + dfs(grid, r, c + 1);
}
/**
* 判断指定坐标是否在网格内
*
* @param grid 表示网格的二维数组
* @param r 行坐标
* @param c 列坐标
* @return 是否在网格内
*/
private boolean isInGrid(int[][] grid, int r, int c) {
return r >= 0 && r < grid.length
&& c >= 0 && c < grid[0].length;
}3.4 最大人工岛
本题选自leetcode第827题：最大人工岛，这一道题是No.695 岛屿的最大面积升级版，难度有所提高。其实我们有了框架，其实想法还是很容易产生的，但是需要注意一些细节问题。我们一起看下题目要求：
题目还是很容易读懂的，其实就是对某个海洋网格进行填海造地，然后找出所有岛屿中最大的岛屿。说到这，我们很容易想到，对某个海洋网格进行填海造地，以实现某个岛屿最大化，我们肯定不会随便找个网格进行填海造地，我们肯定尽量靠近某个已有的岛屿，对其接壤的海洋网格进行填海，这样可以使这个岛屿面积+1，如果对某个海洋网格进行填海造地后，使两个或者更多个本来不接壤的岛屿连接到了一起，那么就有可能形式一个更大的岛屿，基于这种思想，我们来画个图，方便理解。
上图中，红色标注的网格是从海洋填海造陆而来的，图中三个位置，最后求出的最大面积也是不一样的，显然第一个图所构造的人工岛屿面积最大。我们通过在网格中摆动红色网格的位置，可以肉眼看出组成的人工岛屿哪个面积最大，其实思想也应该从摆动的过程中分析出来。我们有两种思路：
- 第一个是依次遍历海洋网格，遍历到海洋网格后，将其
填海造陆，然后按照最大岛屿面积那道题的思路求取面积最大的岛屿，求完之后，再退陆还海再遍历下一个海洋网格，重复操作，直到找到最大的人工岛屿面积； - 第二个是先求取每个岛屿的面积，并记录，然后在遍历海洋网格，看看某个网格与哪些岛屿接壤，当某个海洋网格与一个岛屿接壤的话，那么这个岛屿的面积加1就是人工岛屿的面积，如果与多个岛屿同时接壤，那么将多个岛屿岛屿相加，再加1就是最后人工岛屿的面积，从这些方案中找到最大值即可。
分析了这两种思路，我们觉得，对于第一种，存在可行性，但是由于我们遍历岛屿网格后，会对岛屿网格进行标记，所以第一种方案需要保存最原始的grid对象，后面每次遍历标记都是基于其克隆体来操作，这样就会导致空间复杂度增高，当然时间复杂度也很高，因为每遍历一个海洋网格，我们都要对岛屿网格进行DFS遍历，标记，显然有很多次递归调用，这样效率必然不高。
对于第二种，我们只需要两遍DFS即可。设置一个岛屿编号，可以从2开始（0和1分别是海洋和岛屿，防止混淆），第一遍遍历岛屿网格，算出岛屿的面积，并标记遍历过的岛屿网格的值为岛屿编号，且将编号和岛屿的面积存储到Map中，然后在遍历下一个岛屿，操作方式一致。如下图所示：
第二遍DFS，遍历海洋网格，也就是上面的白色网格，看看每个白色网格都与哪些岛屿网格接壤，如果接壤了，我们就将岛屿的编号存储到Set（去重）中，这样可以防止重复存储相同编号，最后根据编号将岛屿的面积都加到一起，可以比较得出最大的人工岛屿面积。
思路分析道理，我相信读者都应该有了思路，那么如何将这个思路转化成代码呢？读者可以从这里暂停，尝试着自己把上述的思路转化成代码，如果还是有苦难的话，也没关系，可以看下我的代码，根据注释再好好理解一番。
public class No827MakingALargeIsland {
/**
* 两遍DFS求解最大人工岛
*
* @param grid 网格
* @return 最大人工岛
*/
public int largestIsland(int[][] grid) {
// 定义结果
int result = 0;
// 定义岛屿编号，从2开始，0和1分别是海洋和岛屿，防止混淆
int index = 2;
// 定义一个Map，用于存储键为岛屿编号，值为岛屿面积
Map<Integer, Integer> islandAreaMap = new HashMap<>();
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == 1) {
int area = dfs(grid, r, c, index);
islandAreaMap.put(index, area);
index++;
result = Math.max(result, area);
}
}
}
// 如果这个时候result还是0，那么认为没有岛屿，所以这里随便填一个网格就形成了岛屿
if (result == 0) {
return 1;
}
// dfs遍历海洋网格，求取海洋网格相邻的陆地
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == 0) {
// 遍历海洋网格，获取与海洋网格相邻的陆地
Set<Integer> islandIndexSet = findNeighbourIsland(grid, r, c);
// 如果海洋网格没有相邻的岛屿
if (islandIndexSet.size() == 0) {
continue;
}
// 填充这个海洋网格，将该网格相邻的岛屿连接起来
// 该海洋网格面积为1
int tempArea = 1;
for (Integer islandIndex : islandIndexSet) {
tempArea += islandAreaMap.get(islandIndex);
}
// 获取最大面积
result = Math.max(result, tempArea);
}
}
}
return result;
}
/**
* 获取海洋网格周边(上下左右)的相邻岛屿编号
*
* @param grid 网格
* @param r 行坐标
* @param c 列坐标
* @return 岛屿编号Set集合
*/
private Set<Integer> findNeighbourIsland(int[][] grid, int r, int c) {
Set<Integer> islandIndexSet = new HashSet<>();
// 在网格内，且为陆地，只要不为0就是陆地，因为岛屿之前被遍历过，都被修改为了大于等于2以上的数值
if (isInGrid(grid, r - 1, c) && grid[r - 1][c] != 0) {
islandIndexSet.add(grid[r - 1][c]);
}
if (isInGrid(grid, r + 1, c) && grid[r + 1][c] != 0) {
islandIndexSet.add(grid[r + 1][c]);
}
if (isInGrid(grid, r, c - 1) && grid[r][c - 1] != 0) {
islandIndexSet.add(grid[r][c - 1]);
}
if (isInGrid(grid, r, c + 1) && grid[r][c + 1] != 0) {
islandIndexSet.add(grid[r][c + 1]);
}
return islandIndexSet;
}
/**
* 求取岛屿面积且标记遍历过的网格
*
* @param grid 网格
* @param r 行坐标
* @param c 列坐标
* @param index 岛屿编号，将岛屿标记为该值
* @return 岛屿面积
*/
private int dfs(int[][] grid, int r, int c, int index) {
// 超出网格返回或者遍历到海洋，即0，或者已经遍历过的陆地网格（已经被标记为index）
if (!isInGrid(grid, r, c) || grid[r][c] != 1) {
return 0;
}
// 本层要做的事情：标记
grid[r][c] = index;
// 递归计算上下左右网格，求取面积
return 1 + dfs(grid, r - 1, c, index)
+ dfs(grid, r + 1, c, index)
+ dfs(grid, r, c - 1, index)
+ dfs(grid, r, c + 1, index);
}
/**
* 判断指定坐标是否在网格内
*
* @param grid 表示网格的二维数组
* @param r 行坐标
* @param c 列坐标
* @return 是否在网格内
*/
private boolean isInGrid(int[][] grid, int r, int c) {
return r >= 0 && r < grid.length
&& c >= 0 && c < grid[0].length;
}
}上面代码有点多，但是有了详细的注释，相信每一位读者都可以读懂。
至此，几道经典的岛屿类问题，我们都已经得到了解决，读者朋友好好体会一番，尤其要理解我们是如何从二叉树的DFS转移到方向上的DFS，其实这就是简单图的一种DFS思想，希望对读者有所启发。