Skip to content

Number of islands (DFS)

Tim_Gao edited this page Sep 16, 2016 · 1 revision
public class Solution {
    private void populate(char[][] grid, int x, int y){
        if(x<0 || y < 0 || x>=grid.length || y >=grid[0].length || grid[x][y] == '0'){
            return;
        }
        grid[x][y] = '0';
        populate(grid, x-1, y);
        populate(grid, x+1, y);
        populate(grid, x, y+1);
        populate(grid, x, y-1);
    }
    public int numIslands(char[][] grid) {
        int cnt = 0;
        for (int i=0; i<grid.length; ++i){
            for (int j=0; j<grid[0].length; ++j){
                if(grid[i][j] == '1'){
                    ++cnt;
                    populate(grid, i, j);
                }
            }
        }
        return cnt;
    }
}

Clone this wiki locally