200. 岛屿数量

[mengjian-github]

给你一个由 '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  

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/number-of-islands 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[mengjian-github]

这道题本质上和找连通图的问题很像，可以根据dfs来确定一个连通子图，然后转化为找到所有连通子图的问题：

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    const visited = [];
    let result = 0;

    // 初始化二维数组
    for (let i = 0; i < grid.length; i++) {
        visited[i] = [];
    }

    // 一次深度搜索，找出一个岛屿
    function dfs(i, j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) return;
        if (visited[i][j]) return;
        if (grid[i][j] === '0') return;

        visited[i][j] = true;
        // 上下左右四个方向递归
        dfs(i+1, j);
        dfs(i, j+1);
        dfs(i-1, j);
        dfs(i, j-1);
    }

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            // 找出所有为1的起点，没有访问过
            if (grid[i][j] === '1' && !visited[i][j]) {
                dfs(i, j);
                result++;
            }
        }
    }

    return result;
};