岛屿数量

[Cosen95]

leetcode: https://leetcode-cn.com/problems/number-of-islands/

[Cosen95]

题目难度medium，涉及到的算法知识有 DFS（深度优先搜索）。

题目描述

给你一个由  '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

输入:
11110
11010
11000
00000
输出: 1

示例  2:

输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

思路分析

如上图，我们需要计算的就是图中相连（只能是水平和/或竖直方向上相邻）的绿色岛屿的数量。

这道题目一个经典的做法是沉岛，大致思路是：采用DFS（深度优先搜索），遇到 1 的就将当前的 1 变为 0，并将当前坐标的上下左右都执行 dfs，并计数。

终止条件是：超出二维数组的边界或者是遇到 0 ，直接返回。

代码实现

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    const rows = grid.length;
    if (rows === 0) return 0
    const cols = grid[0].length;
    let res = 0;
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === '1') {
                helper(grid, i, j, rows, cols)
                res++
            }
        }
    }
    return res
}
 function helper(grid, i, j, rows, cols) {
    if (i < 0 || j < 0 || i > rows - 1 || j > cols - 1 || grid[i][j] === "0")
        return;

    grid[i][j] = "0"

    helper(grid, i + 1, j, rows, cols);
    helper(grid, i, j + 1, rows, cols);
    helper(grid, i - 1, j, rows, cols);
    helper(grid, i, j - 1, rows, cols);

}