今天是十五周算法训练营的第十五周，主要讲岛屿问题专题。
岛屿问题
一、题目
给你一个由 '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
二、题解
// 找到岛屿+1
// 将岛屿淹没
function numIslands(grid) {
// 通过dfs将岛屿淹没
const dfs = (grid, i, j) => {
const m = grid.length;
const n = grid[0].length;
if (i < 0 || i >= m || j < 0 || j >= n) {
// 超出索引边界
return;
}
// 如果已经被淹了，直接返回
if (grid[i][j] === '0') {
return;
}
// 将当前变成海水
grid[i][j] = '0';
// 淹没四周
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
};
const m = grid.length;
const n = grid[0].length;
let result = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === '1') {
// 每发现一个岛屿，岛屿数量加1
result++;
// 然后使用dfs将岛屿淹没
dfs(grid, i, j);
}
}
}
return result;
}
const grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]];
console.log(numIslands(grid));岛屿的最大面积
一、题目
给你一个大小为 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 解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
二、题解
function maxAreaIsland(grid) {
// 通过dfs淹没岛屿
const dfs = (grid, i, j) => {
const m = grid.length;
const n = grid[0].length;
// 超出边界直接跳过
if (i < 0 || i >= m || j < 0 || j >= n) {
return 0;
}
if (grid[i][j] === 0) {
return 0;
}
// 淹没当前位置
grid[i][j] = 0;
// 淹没上下左右
return 1
+ dfs(grid, i - 1, j)
+ dfs(grid, i + 1, j)
+ dfs(grid, i, j - 1)
+ dfs(grid, i, j + 1);
}
const m = grid.length;
const n = grid[0].length;
let maxArea = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
maxArea = Math.max(dfs(grid, i, j), maxArea);
}
}
}
return maxArea;
}
const 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]];
console.log(maxAreaIsland(grid));飞地的数量
一、题目
给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
示例 1：
输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] 输出：3 解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
二、题解
// 该题目其实就是求不邻接边界的土地的面积
// 其实就是将邻接边界的岛屿淹没，然后遍历一遍获取剩下岛屿的面积
function numsEnclaves(grid) {
// 通过dfs将岛屿淹没
const dfs = (grid, i, j) => {
const m = grid.length;
const n = grid[0].length;
// 超过边界，则跳过
if (i < 0 || i >= m ||j < 0 || j >= n) {
return;
}
// 如果已经是海洋，则跳过
if (grid[i][j] === 0) {
return;
}
// 将当前淹没
grid[i][j] = 0;
// 将上下左右淹没
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
};
let result = 0;
const m = grid.length;
const n = grid[0].length;
// 将上下边界淹没
for (let j = 0; j < n; j++) {
dfs(grid, 0, j);
dfs(grid, m - 1, j);
}
// 将左右边界淹没
for (let i = 0; i < m; i++) {
dfs(grid, i, 0);
dfs(grid, i, n - 1);
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
result++;
}
}
}
return result;
}
const grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]];
console.log(numsEnclaves(grid));统计封闭岛屿的数量
一、题目
二维矩阵 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 区域包围）。
二、题解
// 先将靠边的岛屿淹没掉
// 然后找岛屿，找到岛屿加1，并淹没
function closeIsland(grid) {
// 通过dfs将岛屿淹没
const dfs = (grid, i, j) => {
const m = grid.length;
const n = grid[0].length;
if (i < 0 || i >= m || j < 0 || j >= n) {
return;
}
if (grid[i][j] === 1) {
return;
}
// 将当前位置淹没
grid[i][j] = 1;
// 将上下左右位置淹没
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
};
const m = grid.length;
const n = grid[0].length;
// 将上下边界处的岛屿淹没
for (let j = 0; j < n; j++) {
dfs(grid, 0, j);
dfs(grid, m - 1, j);
}
// 将左右边界的岛屿淹没
for (let i = 0; i < m; i++) {
dfs(grid, i, 0);
dfs(grid, i, n - 1);
}
let result = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 0) {
// 遇到岛屿，岛屿加1
result++;
// 淹没岛屿
dfs(grid, i, j);
}
}
}
return result;
}
const 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]];
console.log(closeIsland(grid));统计子岛屿
一、题目
给你两个 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 个子岛屿。
二、题解
// 首先将在grid1中是海水部分的在grid2中的岛屿淹没掉，剩下的就是grid2中的子岛屿
function countSubIslands(grid1, grid2) {
const dfs = (grid, i, j) => {
const m = grid.length;
const n = grid[0].length;
if (i < 0 || i >= m || j < 0 || j >= n) {
return;
}
if (grid[i][j] === 0) {
return;
}
grid[i][j] = 0;
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
};
// 将grid2中grid1中是海水的岛屿淹没
const m = grid1.length;
const n = grid1[0].length;
let result = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid1[i][j] === 0) {
// 淹没grid2中的岛屿
dfs(grid2, i, j);
}
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid2[i][j] === 1) {
result++;
dfs(grid2, i, j);
}
}
}
return result;
}
const grid1 = [[1,0,1,0,1,1,1,0,1,1,0,1,1,1,1],[1,1,1,1,1,0,1,1,1,1,0,0,0,1,1],[1,1,1,1,1,0,1,1,1,1,1,1,1,1,0],[1,1,1,1,0,1,0,0,1,1,1,1,0,0,1],[0,0,1,1,1,1,1,0,1,0,1,1,1,0,0],[0,1,1,1,1,1,1,1,1,0,1,1,1,1,1],[0,0,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,1,1,1,1,1,1,1,0,1,1,1,1,1,1],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[1,1,1,1,0,1,0,0,1,1,1,0,0,1,1],[1,0,1,1,1,1,1,0,0,1,1,1,1,0,1],[0,1,0,0,0,1,1,1,1,1,1,1,0,0,1]], grid2 = [[1,0,1,0,0,0,1,0,0,0,0,0,1,0,1],[1,1,0,1,0,1,1,1,1,1,0,1,0,1,1],[1,1,1,0,1,1,1,1,1,1,0,1,0,1,1],[1,0,0,1,0,1,1,1,0,0,1,0,1,0,1],[0,1,1,1,1,1,1,0,1,1,1,1,1,0,0],[0,1,1,1,1,1,1,1,1,1,0,1,1,1,0],[1,1,1,1,1,1,1,1,1,0,0,1,0,1,1],[1,0,1,0,0,1,1,1,0,1,0,1,1,1,1],[0,1,0,1,1,1,0,1,1,1,1,0,0,0,1],[1,1,1,0,1,0,0,0,1,1,0,0,1,1,1],[1,0,0,1,1,1,0,0,0,0,1,0,1,0,0],[0,0,1,1,1,1,1,0,1,0,1,1,1,0,0]];
console.log(countSubIslands(grid1, grid2));
