✅200. 岛屿数量

[bazinga-web]

200. 岛屿数量

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

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

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

示例 1:

输入:
11110
11010
11000
00000
输出: 1

示例 2:

输入:
11000
11000
00100
00011
输出: 3

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

[bazinga-web]

解题思路：

1. 遍历二维数组，遇到“1”则让小岛数量加1
2. 然后根据当前位置扩散，使用深度搜索的方式沉没小岛

bfs: （宽）广度优先搜索
dfs: 深度优先搜索

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
    let count = 0;
    function dfs(row, col) {
        if (
            row < 0 ||
            row >= grid.length ||
            col < 0 ||
            col >= grid[0].length ||
            grid[row][col] === "0"
        ) {
            return;
        }
        grid[row][col] = "0";
        dfs(row + 1, col);
        dfs(row - 1, col);
        dfs(row, col + 1);
        dfs(row, col - 1);
    }
    for (let row = 0; row < grid.length; row++) {
        for (let col = 0; col < grid[0].length; col++) {
            if (grid[row][col] === "1") {
                count++;
                dfs(row, col);
            }
        }
    }
    return count;
};

[Ray-56]

深度优先遍历

• 遇到 1 岛屿数量加一的同时调用递归边界判断

function helper(grid, x, y, rowLen, colLen) {
    if (x < 0 || y < 0 || x > rowLen - 1 || y > colLen - 1 || grid[x][y] == '0') return;

    grid[x][y] = '0';

    helper(grid, x - 1, y, rowLen, colLen);
    helper(grid, x + 1, y, rowLen, colLen);
    helper(grid, x, y - 1, rowLen, colLen);
    helper(grid, x, y + 1, rowLen, colLen);
}
/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    // DFS
    let isLand = 0;
    const rowLen = grid.length;
    if (rowLen === 0) return 0;
    const colLen = grid[0].length;

    for (let x = 0; x < rowLen; x++) {
        for (let y = 0; y < colLen; y++) {
            if (grid[x][y] == '1') {
                helper(grid, x, y, rowLen, colLen);
                isLand++;
            }
        }
    }

    return isLand;
};