javascript BSF and DFS solution


  • 0
    3
    DFS solution:
    
    var numIslands = function(grid){
         var numIslandsHelper = function(grid,i,j){
             if(grid[i][j] == 1){
                 grid[i][j] = 0;
             }
             else return;
             if(i-1>=0) numIslandsHelper(grid,i-1,j);
             if(i+1<grid.length) numIslandsHelper(grid,i+1,j);
             if(j-1>=0) numIslandsHelper(grid, i , j-1);
             if(j+1<grid[0].length) numIslandsHelper(grid,i,j+1)
         }
         var count = 0;
         for(var i =0; i<grid.length;i++){
             for(var j = 0; j<grid[0].length;j++){
                 if(i==0&&j==0){
                     numIslandsHelper(grid,i,j);
                     console.log('i is: ', i);
                     console.log("j is: ", j);
                     count++;
                 }
             }
         }
        console.log(grid);
        return count;
    }
    
    BSF solution
    /**
     * @param {character[][]} grid
     * @return {number}
     */
     var Grid = function(x,y){
        this.x = x;
        this.y = y;
    };
    var numIslands = function(grid) {
        var numIslandsHelper = function(grid,i,j){
            var st = new Array();
            if(grid[i][j] == 1){
                grid[i][j] = 0;
                st.push(new Grid(i,j));
            }
            while(st.length>0){
                var length = st.length;
                for(var i = 0; i<length;i++){
                    var coor = st.shift();
                    if(coor.x-1>=0&&grid[coor.x-1][coor.y]==1){
                        grid[coor.x-1][coor.y]=0;
                        st.push(new Grid(coor.x-1,coor.y));
                    }
                    if(coor.x+1<grid.length&&grid[coor.x+1][coor.y]==1){
                        grid[coor.x+1][coor.y]=0;
                        st.push(new Grid(coor.x+1,coor.y));
                    }
                    if(coor.y-1>=0&&grid[coor.x][coor.y-1]==1){
                        grid[coor.x][coor.y-1]=0;
                        st.push(new Grid(coor.x,coor.y-1));
                    }
                    if(coor.y+1<grid[0].length&&grid[coor.x][coor.y+1]==1){
                        grid[coor.x][coor.y+1]=0;
                        st.push(new Grid(coor.x,coor.y+1));
                    }
                }
            }
        }
        var count=0;
        for(var i=0; i<grid.length;i++){
            for(var j = 0; j<grid[0].length;j++){
                if(grid[i][j] == 1){
                    numIslandsHelper(grid,i,j);
                    count++;
                }
            }
        }
        return count;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.