JAVA solution, inspired by the DFS C++ next door. Come and conquer, destroy all.


  • 0
    R

    Shamed that I just complained about it under that C++ solution sharing topic, and I did the same thing. I altered the input 'grid', which I believe that would be improper while build a real API.

    The basic idea is to DESTROY all the islands the program find and get the linked '1's.

    I think the desetroy process could be improved, since some of the positions on grid has been judged more than one time.

    public class Solution {
    public int numIslands(char[][] grid) {
        if(grid==null||grid.length<=0) return 0;
        int height=grid.length;
        int width=grid[0].length;
        int ans=0;
        for(int i=0;i<height;i++){
            for(int j=0;j<width;j++){
                if(grid[i][j]=='1'){
                    destroyIsland(grid,i,j);
                    ans++;
                }
            }
        }
        return ans;
    }
    public static void destroyIsland(char[][] grid, int x, int y){
        grid[x][y]='0';
        if(x-1>=0 && grid[x-1][y]=='1') destroyIsland(grid,x-1,y);
        if(y-1>=0 && grid[x][y-1]=='1') destroyIsland(grid,x,y-1);
        if(x+1<grid.length && grid[x+1][y]=='1') destroyIsland(grid,x+1,y);
        if(y+1<grid[x].length && grid[x][y+1]=='1') destroyIsland(grid,x,y+1);
    }
    

    }


Log in to reply
 

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