https://leetcode.com/problems/number-of-islands/
Approach #1 DFS [Accepted]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
private void dfs(char[][] grid,int nr,int nc,int r,int c){
if(r<0||r>=nr||c<0||c>=nc||grid[r][c]=='0') return;
grid[r][c]='0';
dfs(grid,nr,nc,r-1,c);
dfs(grid,nr,nc,r+1,c);
dfs(grid,nr,nc,r,c-1);
dfs(grid,nr,nc,r,c+1);
}
public int numIslands(char[][] grid) {
if(grid==null||grid.length==0) return 0;
int nr=grid.length;
int nc=grid[0].length;
int numIslands=0;
for(int r=0;r<nr;r++){
for(int c=0;c<nc;c++){
if(grid[r][c]=='1'){
numIslands++;
dfs(grid,nr,nc,r,c);
}
}
}
return numIslands;
}
}
Approach #2: BFS [Accepted]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
98class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
grid[r][c] = '0'; // mark as visited
LinkedList<Integer[]> neighbors = new LinkedList();
neighbors.add(new Integer[]{r,c});
while (!neighbors.isEmpty()) {
Integer[] id = neighbors.remove();
int row = id[0];
int col = id[1];
if (row - 1 >= 0 && grid[row-1][col] == '1') {
neighbors.add(new Integer[]{row-1,col});
grid[row-1][col] = '0';
}
if (row + 1 < nr && grid[row+1][col] == '1') {
neighbors.add(new Integer[]{row+1,col});
grid[row+1][col] = '0';
}
if (col - 1 >= 0 && grid[row][col-1] == '1') {
neighbors.add(new Integer[]{row,col-1});
grid[row][col-1] = '0';
}
if (col + 1 < nc && grid[row][col+1] == '1') {
neighbors.add(new Integer[]{row,col+1});
grid[row][col+1] = '0';
}
}
}
}
}
return num_islands;
}
}
/*
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
grid[r][c] = '0'; // mark as visited
// LinkedList<List<Integer>> neighbors = new LinkedList();
// neighbors.add(new LinkedList<Integer>(Arrays.asList(r, c)));
LinkedList<Integer[]> neighbors = new LinkedList();
neighbors.add(new Integer[]{r,c});
while (!neighbors.isEmpty()) {
// List<Integer> id = neighbors.remove();
Integer[] id = neighbors.remove();
// int row = id.get(0);
// int col = id.get(1);
int row = id[0];
int col = id[1];
if (row - 1 >= 0 && grid[row-1][col] == '1') {
// neighbors.add(new LinkedList<Integer>(Arrays.asList(row-1,col)));
neighbors.add(new Integer[]{row-1,col});
grid[row-1][col] = '0';
}
if (row + 1 < nr && grid[row+1][col] == '1') {
// neighbors.add(new LinkedList<Integer>(Arrays.asList(row+1,col)));
neighbors.add(new Integer[]{row+1,col});
grid[row+1][col] = '0';
}
if (col - 1 >= 0 && grid[row][col-1] == '1') {
// neighbors.add(new LinkedList<Integer>(Arrays.asList(row,col-1)));
neighbors.add(new Integer[]{row,col-1});
grid[row][col-1] = '0';
}
if (col + 1 < nc && grid[row][col+1] == '1') {
// neighbors.add(new LinkedList<Integer>(Arrays.asList(row,col+1)));
neighbors.add(new Integer[]{row,col+1});
grid[row][col+1] = '0';
}
}
}
}
}
return num_islands;
}
}*/
concise version
REF.
Approach #3: Union Find (aka Disjoint Set) [Accepted]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
83class UF {
public int count = 0;
public int[] parent = null;
public UF(int m, int n, char[][] grid) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') count++;
}
}
parent = new int[m * n];
for (int i = 0; i < m * n; i++) {
parent[i] = i;
}
}
public int find(int x) {
while (x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
/*public boolean isConnected(int x, int y) {
int pRoot = find(x);
int qRoot = find(y);
if (pRoot != qRoot)
return false;
else
return true;
}*/
public void union(int x, int y) {
int pRoot = find(x);
int qRoot = find(y);
if(pRoot == qRoot) return;
parent[pRoot] = qRoot;
count--;
}
}
public class test {
public static int numIslands(char[][] grid) {
if (grid.length == 0 || grid[0].length == 0) return 0;
int m = grid.length, n = grid[0].length;
UF uf = new UF(m, n, grid);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '0') continue;
int x = i * n + j;
int y;
if (i > 0 && grid[i - 1][j] == '1') {
y = x - n;
uf.union(x, y);
}
if (i < m - 1 && grid[i + 1][j] == '1') {
y = x + n;
uf.union(x, y);
}
if (j > 0 && grid[i][j - 1] == '1') {
y = x - 1;
uf.union(x, y);
}
if (j < n - 1 && grid[i][j + 1] == '1') {
y = x + 1;
uf.union(x, y);
}
}
}
return uf.count;
}
public static void main(String[] args) {
char[][] charArr = {
{ '1', '1', '0', '0', '0' },
{ '1', '1', '0', '0', '0' },
{ '0', '0', '1', '0', '0' },
{ '0', '0', '0', '1', '1' } };
System.out.println(numIslands(charArr));
}
}