fishercoderLeetcode/MEDIUM/src/medium/NumberofIslandsDFS.java at master · JesusCoder/fishercoderLeetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package medium;

/**
 * Created by fishercoder1534 on 9/29/16.
 */
public class NumberofIslandsDFS {


    public static int numIslands(char[][] grid) {
        if(grid == null || grid.length == 0) return 0;
        int count = 0;
        int m = grid.length, n = grid[0].length;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1'){
                    count++;
                    dfs(grid, i, j, m, n);
                }
            }
        }
        return count;
    }

    static void dfs(char[][] grid, int i, int j, int m, int n){
        if(i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') return;
        grid[i][j] = '0';
        dfs(grid, i+1, j, m, n);
        dfs(grid, i, j+1, m, n);
        dfs(grid, i-1, j, m, n);
        dfs(grid, i, j-1, m, n);
    }


    public static void main(String...args){
//        char[][] grid = new char[][]{
//                {'1','1','1','1','0'},
//                {'1','1','0','1','0'},
//                {'1','1','0','0','0'},
//                {'0','0','0','0','0'},
//        };

//        ["11000","11000","00100","00011"]
//        char[][] grid = new char[][]{
//                {'1','1','0','0','0'},
//                {'1','1','0','0','0'},
//                {'0','0','1','0','0'},
//                {'0','0','0','1','1'},
//        };

//        ["111","010","111"]
        //doing normal row by row and column by column scan will fail by this test case:
        //when encountering grid[2][0], grid[2][1] hasn't been marked to '#' yet, so, it'll count grid[2][0] as a new island, which
        //in fact it is not!
        //So, we must apply DFS, so how does Union Find work?
        char[][] grid = new char[][]{
                {'1','1','1'},
                {'0','1','0'},
                {'1','1','1'},
        };
        System.out.println(numIslands(grid));
    }
}