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.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[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;
};

代码分析

1. var numIslands = function(grid) {
   定义了一个名为 numIslands 的函数，它接受一个二维数组 grid 作为参数。

2. let count = 0;
   声明一个变量 count 用来计数岛屿的数量，初始值为 0。

3. let m = grid.length;
   获取网格的行数。

4. let n = grid[0].length;
   获取网格的列数。

5. const dfs = (i, j) => {
   定义一个名为 dfs 的函数，它接受两个参数 i 和 j，分别代表当前要访问的网格的行和列的索引。

6. if(i < 0 || j < 0 || i >= m || j >= n || grid[i][j] === '0') return;
   这是一个边界检查，确保不会访问网格外的元素，并且只有当当前位置是陆地（即 grid[i][j] 的值为 ‘1’）时，才会继续执行。

7. grid[i][j] = '0';
   将当前位置标记为已访问，通过将其值改为 '0'。

8. dfs(i + 1, j);
   递归调用 dfs 函数，检查当前位置的下方是否有陆地。

9. dfs(i - 1, j);
   递归调用 dfs 函数，检查当前位置的上方是否有陆地。

10. dfs(i, j + 1);
    递归调用 dfs 函数，检查当前位置的右侧是否有陆地。

11. dfs(i, j - 1);
    递归调用 dfs 函数，检查当前位置的左侧是否有陆地。

12. for(let i = 0; i < m; i++) {
    开始一个外层循环，遍历每一行。

13. for(let j = 0; j < n; j++) {
    开始一个内层循环，遍历每一列。

14. if(grid[i][j] === '1') {
    检查当前位置是否是陆地。

15. dfs(i, j);
    如果是陆地，调用 dfs 函数，从这个位置开始进行深度优先搜索，将整个岛屿标记为已访问。

这里每一块陆地通过这个函数都会变为海洋，不会影响其他陆地的搜索，下面直接统计数量

17. count++;
    每找到一个岛屿，岛屿计数器 count 增加 1。

18. return count;
    返回岛屿的总数。

这段代码的总体思路是使用深度优先搜索（DFS）来遍历整个网格。对于每个未被访问的陆地单元格，它都会递归地标记所有相邻的陆地单元格，直到没有更多的陆地可以访问。每完成一次这样的搜索，就意味着找到了一个岛屿，因此增加岛屿的计数。这个过程会一直重复，直到所有的陆地都被访问过。最后，函数返回找到的岛屿总数。