prep-coding/leetcode/NumberOfIslands.java at master · tushar-sharma/prep-coding · 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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
 * leetcode: https://leetcode.com/problems/number-of-islands/
 */
import java.util.Arrays;

public class NumberOfIslands{

    public static int dfs(char[][] grid, int i , int j, boolean[][] visited) {

        visited[i][j] = true;

        if ( (i + 1) < grid.length && grid[i + 1][j]  == '1' && visited[i + 1][j] == false) {
            dfs(grid, i + 1, j , visited);
        }

        if ( (i - 1) >= 0 && grid[i - 1][j]  == '1' && visited[i - 1][j] == false) {
            dfs(grid, i - 1, j , visited);
        }


        if ( (j + 1) < grid[0].length && grid[i][j + 1]  == '1' && visited[i][j + 1] == false) {
            dfs(grid, i, j + 1 , visited);

        }

        if ( (j - 1) >= 0 && grid[i][j - 1]  == '1' && visited[i][j - 1] == false) {
            dfs(grid, i, j - 1 , visited);

        }

        return 1;
    }

    public static int numIslands(char[][] grid) {
        int count = 0;

        if (grid.length < 0) {
            return count;
        }

        int length = grid.length;
        int breadth = grid[0].length;

        boolean[][] visited = new boolean[length][breadth];

        for (int i = 0; i < length; i++) {
            for (int j = 0; j < breadth; j++) {
                if (visited[i][j] == false && grid[i][j] == '1') {
                    count += dfs(grid, i, j, visited);
                }
            }
        }

        return count;

    }

    public static void main(String[] args) {

        char[][] grid1 = new char[][]{
                                      {'1', '1', '1', '1', '0'},
                                      {'1', '1', '0', '1', '0'},
                                      {'1', '1', '0', '0', '0'},
                                      {'0', '0', '0', '0', '0'}
                                  };

        char[][] grid2 = new char[][]{
                                      {'1', '1', '0', '0', '0'},
                                      {'1', '1', '0', '0', '0'},
                                      {'0', '0', '1', '0', '0'},
                                      {'0', '0', '0', '1', '1'}
                                  };

        char[][] grid3 = new char[][]{
                                      {'1', '1', '1'},
                                      {'0', '1', '0'},
                                      {'1', '1', '1'}
                                  };


        assert numIslands(grid1) == 1;

        assert numIslands(grid2) == 3;

        assert numIslands(grid3) == 1;
    }
}