Java concise DFS solution


  • 0
    M
    public int numIslands(char[][] grid) {
        if(grid.length==0){
            return 0;
        }
        int island=0;
        boolean[][] visited=new boolean[grid.length][grid[0].length];
        for(int i=0;i<visited.length;i++){
            Arrays.fill(visited[i],false);
        }
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(!visited[i][j] && grid[i][j]=='1'){
                    island++;
                    visited[i][j]=true;
                    expand(grid,visited,i,j);
                }
            }
        }
        return island;
    }
    public void expand(char[][] grid, boolean[][] visited,int i,int j){
        if(i>0 && !visited[i-1][j] && grid[i-1][j]=='1'){
            visited[i-1][j]=true;
            expand(grid,visited,i-1,j);
        }
        if(i<grid.length-1 && !visited[i+1][j] && grid[i+1][j]=='1'){
            visited[i+1][j]=true;
            expand(grid,visited,i+1,j);
        }
        if(j>0 && !visited[i][j-1] && grid[i][j-1]=='1'){
            visited[i][j-1]=true;
            expand(grid,visited,i,j-1);
        }
        if(j<grid[0].length-1 && !visited[i][j+1] && grid[i][j+1]=='1'){
            visited[i][j+1]=true;
            expand(grid,visited,i,j+1);
        }
    }

Log in to reply
 

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