岛屿的个数

[JesseZhao1990]

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    var res =0;
    var visited =[];
    var m = grid.length;
    if(grid.length===0) return res;
    var n = grid[0].length;
    var d = [[0,1],[1,0],[0,-1],[-1,0]];
    
    // 初始化visited
    for(var i=0;i<grid.length;i++){
        visited.push(new Array(grid[0].length).fill(false));
    }
    
    for(var i=0;i<m;i++){
        for(var j=0;j<n;j++){
            if(inArea(i,j) && !visited[i][j] && grid[i][j] !== "0"){
                res++;
                dfs(grid,i,j);
            }
        }
    }
    
    return res;
    
    // 判断是否在网格中
    function inArea(i,j){
        return i>=0 && j>=0 && i<m && j<n;
    }
    
    // 深度优先遍历，递归去标记是否已经被访问过
    function dfs(grid,i,j){
        visited[i][j] = true;
        for(var k=0;k<4;k++){
            var newI = i+d[k][0];
            var newJ = j+d[k][1];
            if(inArea(newI,newJ) && grid[newI][newJ] !=="0" && !visited[newI][newJ]){
                dfs(grid,newI,newJ);
            }
        }
    }
    
    
};

// var grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]];
// console.log(numIslands(grid));

解题思路：

遍历二维数组，在每个点再进行深度优先遍历，标记是否已经访问过。

leetcode原题地址：https://leetcode-cn.com/problems/number-of-islands/description/