岛屿算法（求岛屿数量与岛屿面积）
Author：zhoulujun Date：
LeetCode算法按照类型分类，常见的算法类型包括：
递归和回溯
深度优先搜索（DFS）和广度优先搜索（BFS）
双指针
动态规划
贪心算法
二分搜索
排序算法
并查集
分治算法
位运算
岛屿算法涉及 深度优先搜索（DFS）、广度优先搜索（BFS）、并查集（Union Find），核心考点就是用 DFS/BFS 算法遍历二维数组。
岛屿问题是经典的面试高频题，虽然基本的岛屿问题并不难，但是岛屿问题有一些有意思的扩展，比如求子岛屿数量，求形状不同的岛屿数量等等
一般的岛屿算法题如下：
https://leetcode-cn.com/problems/number-of-islands/
给你一个由 '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
示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
根据 《算法与数据结构面试通关经验总结：leetCode刷题经验》与 《讲透学烂二叉树(三)：二叉树的遍历图解算法步骤及JS代码》
先后、中序、后续总结
几乎所有二叉树的题目都是一套这个框架就出来了：
递归
postOrderTraverse (node) { // 数组存储数遍历值 let backs = [] // 递归， function tempFunction (node) { if (node.data !== null) { // 先序 backs.push(node.data) node.leftChild && tempFunction(node.leftChild) // 中序 backs.push(node.data) node.rightChild && tempFunction(node.rightChild) // 后续 backs.push(node.data) } } tempFunction(node) return backs }核心架构
function traverse (root) { // 前序位置 traverse(root.left); // 中序位置 traverse(root.right); // 后序位置}
完全可以根据二叉树的遍历框架改写出二维矩阵的 DFS 代码框架：
function dfs(grid, i, j) {
// 超出索引边界
if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length) {
return 0;
}
// 已经是海水了
if(grid[i][j] === '0'){
return 0;
}
// 标记为已访问，已经访问过的，直接标记为海水即可，即 (i, j) 变成海水 '0'
grid[i][j] = '0';
// 淹没上下左右的陆地
dfs(grid, i - 1, j);// 上
dfs(grid, i + 1, j);// 下
dfs(grid, i, j - 1);// 左
dfs(grid, i, j + 1);// 右
return 1; // 找到一个岛屿后返回1
}所以算法如下：
function numIslands(grid) {
if (!grid || grid.length === 0) {
return 0;
}
const rows = grid.length, cols = grid[0].length;
let numIslands = 0;
for (let i = 0; i < rows; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === '1') {
numIslands += dfs(grid, i, j);
}
}
}
return numIslands;
}为什么每次遇到岛屿，都要用 DFS 算法把岛屿「淹了」呢？
主要是为了省事，避免维护 visited 数组。
因为 dfs 函数遍历到值为 0 的位置会直接返回，所以只要把经过的位置都设置为 0，就可以起到不走回头路的作用。
这类 DFS 算法还有个别名叫做 FloodFill 算法，现在有没有觉得 FloodFill 这个名字还挺贴切的~
这个最最基本的岛屿问题就说到这，我们来看看后面的题目有什么花样。
封闭岛屿的数量
上一题说二维矩阵四周可以认为也是被海水包围的，所以靠边的陆地也算作岛屿。
力扣第 1254 题「统计封闭岛屿的数目」和上一题有两点不同：
用 0 表示陆地，用 1 表示海水。
让你计算「封闭岛屿」的数目。所谓「封闭岛屿」就是上下左右全部被 1 包围的 0，也就是说靠边的陆地不算作「封闭岛屿」。
算法返回 2，只有图中灰色部分的 0 是四周全都被海水包围着的「封闭岛屿」。
那么如何判断「封闭岛屿」呢？
其实很简单，把上一题中那些靠边的岛屿排除掉，剩下的不就是「封闭岛屿」了吗？
function closedIsland(grid) {
let rows = grid.length;
let cols = grid[0].length;
// Step 1: Exclude islands connected to the borders
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
// 通过if条件判断当前元素是否位于边界，是的话就执行dfs。
if (i === 0 || i === rows - 1 || j === 0 || j === cols - 1) {
dfs(i, j); // Exclude islands connected to the border
}
}
}
/** 这种写法更为精确，直接针对矩阵的四条边界进行遍历，首先遍历上下边界，然后遍历左右边界。这种方法避免了不必要的迭代和判断，因为它直接指定了边界元素的位置，所以每次迭代都会调用dfs，没有多余的操作。
// 淹掉靠边的岛屿
for (let j = 0; j < cols; j++) {
dfs(0, j); // 上边界
dfs(rows - 1, j); // 下边界
}
for (let i = 0; i < rows; i++) {
dfs(i, 0); // 左边界
dfs(i, cols - 1); // 右边界
}
*/
// Step 2: Count the number of closed islands
let count = 0;
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (grid[i][j] === 0) {
count++;
dfs(i, j); // Mark the closed island as visited
}
}
}
return count;
}岛屿的最大面积
695.岛屿的最大面积，0 表示海水，1 表示陆地，现在不让你计算岛屿的个数了，而是让你计算最大的那个岛屿的面积
这题的大体思路和之前完全一样，只不过 dfs 函数淹没岛屿的同时，还应该想办法记录这个岛屿的面积。
DNS算法
function dfs(i, j) {
// 如果位置不合法或者该位置不是陆地，则返回0
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) {
return 0;
}
// 将当前的陆地标记为已访问
grid[i][j] = 0;
// 当前岛屿的面积为1加上上下左右四个方向上陆地的面积
let area = 1;
// 向上探索
area += dfs(i - 1, j);
// 向下探索
area += dfs(i + 1, j);
// 向左探索
area += dfs(i, j - 1);
// 向右探索
area += dfs(i, j + 1);
return area;
}递归
function maxAreaOfIsland(grid) {
let maxArea = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
// 遇到陆地启动DFS
if (grid[i][j] == 1) {
maxArea = Math.max(maxArea, dfs(i, j));
}
}
}
return maxArea;
}解法和之前相比差不多，我也不多说了，接下来的两道岛屿问题是比较有技巧性的，我们重点来看一下。
子岛屿数量
给你两个mxn的二进制矩阵 grid1和grd2，它们只包含 0 (表示水域)和1(表示陆地）一个 岛屿 是由四个方向(水平或者竖直) 上相的 1组成的区域。任何矩阵以外的区域都视为水域。
如果 grid2的一个岛屿，被 grid1 的一个岛屿完全包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1中同一个 岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿。
请你返回 grid2中子岛屿的数目
You are given two m x n binary matrices grid1 and grid2 containing only 0's (representing water) and 1's (representing land). An island is a group of 1's connected 4-directionally (horizontal or vertical). Any cells outside of the grid are considered water cells.
An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2.
Return the number of islands in grid2 that are considered sub-islands.
Example 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 : In the picture above, the grid on the left is grid1 and the grid on the right is grid2. The 1s colored red in grid2 are those considered to be part of a sub-island. There are three sub-islands.Example 2:
: grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]] : 2 : In the picture above, the grid on the left is grid1 and the grid on the right is grid2. The 1s colored red in grid2 are those considered to be part of a sub-island. There are two sub-islands.
这道题的关键在于，如何快速判断子岛屿？肯定可以借助 Union Find 并查集算法 来判断，不过本文重点在 DFS 算法，就不展开并查集算法了。
什么情况下 grid2 中的一个岛屿 B 是 grid1 中的一个岛屿 A 的子岛？
当岛屿 B 中所有陆地在岛屿 A 中也是陆地的时候，岛屿 B 是岛屿 A 的子岛。
反过来说，如果岛屿 B 中存在一片陆地，在岛屿 A 的对应位置是海水，那么岛屿 B 就不是岛屿 A 的子岛。
那么，我们只要遍历 grid2 中的所有岛屿，把那些不可能是子岛的岛屿排除掉，剩下的就是子岛。
function countSubIslands(grid1, grid2) {
const row = grid2.length;
const col = grid2[0].length;
let count = 0;
function (i, j) {
if (i < 0 || j < 0 || i >= row || j >= col || grid2[i][j] == 0) return true;
// 如果 grid2 中某位置是陆地而 grid1 不是，直接返回 false
if (grid1[i][j] == 0) return false;
// 标记当前位置已访问
grid2[i][j] = 0;
let res = true;
// 遍历上下左右四个方向
res &= dfs(i + 1, j);
res &= dfs(i - 1, j);
res &= dfs(i, j + 1);
res &= dfs(i, j - 1);
return res;
};
for (let i = 0; i < row; i++) {
for (let j = 0; j < col; j++) {
// 只对grid2中的岛屿部分进行DFS
if (grid2[i][j] == 1) {
// 如果DFS返回true，则意味着当前岛屿被完全包含，子岛屿数量+1
if (dfs(i, j)) count += 1;
}
}
}
return count;
}不同的岛屿数量
力扣第 694 题 不同的岛屿数量, 题目还是输入一个二维矩阵，0 表示海水，1 表示陆地，这次让你计算 不同的 (distinct) 岛屿数量
其中有四个岛屿，但是左下角和右上角的岛屿形状相同，所以不同的岛屿共有三个，算法返回 3。
很显然我们得想办法把二维矩阵中的「岛屿」进行转化，变成比如字符串这样的类型，然后利用 HashSet 这样的数据结构去重，最终得到不同的岛屿的个数。
如果想把岛屿转化成字符串，说白了就是序列化，序列化说白了就是遍历嘛，前文 二叉树的序列化和反序列化 讲了二叉树和字符串互转，这里也是类似的。
首先，对于形状相同的岛屿，如果从同一起点出发，dfs 函数遍历的顺序肯定是一样的。
function numDistinctIslands(grid) {
let distinctIslands = new Set(); // 用于存储不同岛屿的集合
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === 1) {
let path = []; // 存储当前岛屿的路径
dfs(grid, i, j, path, 'o'); // 使用'o'作为起点方向
distinctIslands.add(path.join('')); // 将路径转换为字符串，添加到集合中
}
}
}
return distinctIslands.size; // 返回不同岛屿的数量
}
function dfs(grid, i, j, path, dir) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] === 0) {
return;
}
grid[i][j] = 0; // 标记当前陆地为已访问
path.push(dir); // 记录方向
dfs(grid, i - 1, j, path, 'u'); // 向上
dfs(grid, i + 1, j, path, 'd'); // 向下
dfs(grid, i, j - 1, path, 'l'); // 向左
dfs(grid, i, j + 1, path, 'r'); // 向右
path.push('b'); // 回溯标记
}
// 测试代码
let grid = [
[1, 1, 0, 0, 0],
[1, 1, 0, 0, 0],
[0, 0, 0, 1, 1],
[0, 0, 0, 1, 1]
];
console.log(numDistinctIslands(grid)); // 输出不同的岛屿数量参考文章：
DFS 算法秒杀五道岛屿问题 https://zhuanlan.zhihu.com/p/426102881
转载本站文章《岛屿算法（求岛屿数量与岛屿面积）》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9148.html