LeetCode岛屿数量
题目描述
给你一个由 '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
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j] 的值为 '0' 或 '1'
解题思路
岛屿问题是网格 DFS 问题的典型代表，我们所熟悉的 DFS（深度优先搜索）问题通常是在树或者图结构上进行的。而岛屿 DFS 问题，是在一种「网格」结构中进行的。
我们首先明确一下岛屿问题中的网格结构是如何定义的，以方便我们后面的讨论。
网格问题是由 m×n 个小方格组成一个网格，每个小方格与其上下左右四个方格认为是相邻的，要在这样的网格上进行某种搜索。
岛屿问题是一类典型的网格问题。每个格子中的数字可能是 0 或者 1。我们把数字为 0 的格子看成海洋格子，数字为 1 的格子看成陆地格子，这样相邻的陆地格子就连接成一个岛屿。
网格结构中的格子有多少相邻结点？答案是上下左右四个。对于格子 (r, c) 来说（r 和 c 分别代表行坐标和列坐标），四个相邻的格子分别是 (r-1, c)、(r+1, c)、(r, c-1)、(r, c+1)。换句话说，网格结构是「四叉」的。
代码
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
//深度优先
let count = 0;
let m = grid.length;
let n = grid[0].length;
const dfs = (i, j) => {
if(i < 0 || j < 0 || i >= m || j >= n || grid[i][j] === '0') return;//下标越界或不是陆地，返回
grid[i][j] = '0';//将陆地置为水，避免后续访问重复计算这个位置
//检验它的上下左右方向有没有陆地
dfs(i + 1, j);
dfs(i - 1, j);
dfs(i, j + 1);
dfs(i, j - 1);
}
for(let i = 0; i < m; i++) {
for(let j = 0; j < n; j++) {
if(grid[i][j] === '1') {//找到陆地
dfs(i, j);//找到这个陆地所属的一整块岛屿，整个岛屿原本的的'1'都被置为'0'
count++;//岛屿数量增加
}
}
}
return count;
};
代码分析
-
var numIslands = function(grid) {
定义了一个名为numIslands的函数，它接受一个二维数组grid作为参数。 -
let count = 0;
声明一个变量count用来计数岛屿的数量，初始值为 0。 -
let m = grid.length;
获取网格的行数。 -
let n = grid[0].length;
获取网格的列数。 -
const dfs = (i, j) => {
定义一个名为dfs的函数，它接受两个参数i和j，分别代表当前要访问的网格的行和列的索引。 -
if(i < 0 || j < 0 || i >= m || j >= n || grid[i][j] === '0') return;
这是一个边界检查，确保不会访问网格外的元素，并且只有当当前位置是陆地（即grid[i][j]的值为 ‘1’）时，才会继续执行。 -
grid[i][j] = '0';
将当前位置标记为已访问，通过将其值改为'0'。 -
dfs(i + 1, j);
递归调用dfs函数，检查当前位置的下方是否有陆地。 -
dfs(i - 1, j);
递归调用dfs函数，检查当前位置的上方是否有陆地。 -
dfs(i, j + 1);
递归调用dfs函数，检查当前位置的右侧是否有陆地。 -
dfs(i, j - 1);
递归调用dfs函数，检查当前位置的左侧是否有陆地。 -
for(let i = 0; i < m; i++) {
开始一个外层循环，遍历每一行。 -
for(let j = 0; j < n; j++) {
开始一个内层循环，遍历每一列。 -
if(grid[i][j] === '1') {
检查当前位置是否是陆地。 -
dfs(i, j);
如果是陆地，调用dfs函数，从这个位置开始进行深度优先搜索，将整个岛屿标记为已访问。
这里每一块陆地通过这个函数都会变为海洋，不会影响其他陆地的搜索，下面直接统计数量
-
count++;
每找到一个岛屿，岛屿计数器count增加 1。 -
return count;
返回岛屿的总数。
这段代码的总体思路是使用深度优先搜索（DFS）来遍历整个网格。对于每个未被访问的陆地单元格，它都会递归地标记所有相邻的陆地单元格，直到没有更多的陆地可以访问。每完成一次这样的搜索，就意味着找到了一个岛屿，因此增加岛屿的计数。这个过程会一直重复，直到所有的陆地都被访问过。最后，函数返回找到的岛屿总数。