-
Notifications
You must be signed in to change notification settings - Fork 2
/
NumberOfIslands.java
105 lines (91 loc) · 2.77 KB
/
NumberOfIslands.java
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
package Leetcode;
import java.util.Deque;
import java.util.LinkedList;
/**
* @author kalpak
*
* Given an m x n 2d grid map of '1's (land) and '0's (water), return the number of islands.
* An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
*
* You may assume all four edges of the grid are all surrounded by water.
*
* Example 1:
* Input: grid = [
* ["1","1","1","1","0"],
* ["1","1","0","1","0"],
* ["1","1","0","0","0"],
* ["0","0","0","0","0"]
* ]
* Output: 1
*
*
* Example 2:
* Input: grid = [
* ["1","1","0","0","0"],
* ["1","1","0","0","0"],
* ["0","0","1","0","0"],
* ["0","0","0","1","1"]
* ]
*
* Output: 3
*
* Constraints:
*
* m == grid.length
* n == grid[i].length
* 1 <= m, n <= 300
* grid[i][j] is '0' or '1'.
*
*/
public class NumberOfIslands {
static int[][] directions = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
public static int numIslands(char[][] grid) {
int result = 0;
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
if(grid[i][j] == '1') {
dfsDetectIslands(grid, i, j);
result++;
}
}
}
return result;
}
private static void dfsDetectIslands(char[][] grid, int i, int j) {
// edge cases
if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0')
return;
// Mark the cell as visited
grid[i][j] = '0';
// traverse in all possible direction
dfsDetectIslands(grid, i+1, j);
dfsDetectIslands(grid, i-1, j);
dfsDetectIslands(grid, i, j+1);
dfsDetectIslands(grid, i, j-1);
return;
}
private static void bfsDetectIslands(char[][] grid, int i, int j) {
Deque<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
// Mark the cell as visited
grid[i][j] = '0';
while(!queue.isEmpty()) {
int[] currentIdx = queue.poll();
for(int[] dir : directions) {
int row = currentIdx[0] + dir[0];
int col = currentIdx[1] + dir[1];
// edge cases
if(row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == '0')
continue;
// Mark the cell as visited
grid[row][col] = '0';
queue.offer(new int[]{row, col});
}
}
}
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'}};
System.out.println(numIslands(grid));
}
}