高端网站登录入口,seo关键词推广多少钱,做一个旅游网站,2017学脚本语言做网站题目描述
有一个二维矩阵 grid #xff0c;每个位置要么是陆地#xff08;记号为 0 #xff09;要么是水域#xff08;记号为 1 #xff09;。我们从一块陆地出发#xff0c;每次可以往上下左右 4 个方向相邻区域走#xff0c;能走到的所有陆地区域#xff0c;我们将其…题目描述
有一个二维矩阵 grid 每个位置要么是陆地记号为 0 要么是水域记号为 1 。我们从一块陆地出发每次可以往上下左右 4 个方向相邻区域走能走到的所有陆地区域我们将其称为一座「岛屿」。如果一座岛屿 完全 由水域包围即陆地边缘上下左右所有相邻区域都是水域那么我们将其称为 「封闭岛屿」。请返回封闭岛屿的数目。输入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 区域包围。
输入grid [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
输出1
输入grid [[1,1,1,1,1,1,1],[1,0,0,0,0,0,1],[1,0,1,1,1,0,1],[1,0,1,0,1,0,1],[1,0,1,1,1,0,1],[1,0,0,0,0,0,1],[1,1,1,1,1,1,1]]
输出2思路
先把跟边界连通的 0 变成 1 (或者其他占位符)然后计算其他连通的 0 有多少组。
复杂度
时间复杂度$O(m*n)$m 和 n 是 grid 的长宽。空间复杂度$O(max(m, n))$递归栈的空间我感觉是这个。
代码
JavaScript Code
/*** param {number[][]} grid* return {number}*/
var closedIsland function (grid) {const outOfBoundary (grid, x, y) x 0 || x grid.length || y 0 || y grid[0].length;const dfs (grid, x, y) {if (outOfBoundary(grid, x, y)) return false;if (grid[x][y] 1) return true;grid[x][y] 1;if (dfs(grid, x - 1, y) dfs(grid, x 1, y) dfs(grid, x, y - 1) dfs(grid, x, y 1))return true;return false;};const mark (grid, x, y) {if (outOfBoundary(grid, x, y) || grid[x][y] 1) return;grid[x][y] 1;mark(grid, x - 1, y);mark(grid, x 1, y);mark(grid, x, y - 1);mark(grid, x, y 1);};// 将连通边界的 0 都改成 1for (let i 0; i grid.length; i) {mark(grid, i, 0);mark(grid, i, grid[0].length - 1);}for (let j 0; j grid[0].length; j) {mark(grid, 0, j);mark(grid, grid.length - 1, j);}let ans 0;for (let i 0; i grid.length; i) {for (let j 0; j grid[0].length; j) {if (grid[i][j] 1) continue;if (dfs(grid, i, j)) ans;}}return ans;
};
