-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathNumberOfIslands.java
More file actions
110 lines (101 loc) · 3.19 KB
/
NumberOfIslands.java
File metadata and controls
110 lines (101 loc) · 3.19 KB
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
106
107
108
109
110
//给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
//
// 岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
//
// 此外，你可以假设该网格的四条边均被水包围。
//
//
//
// 示例 1:
//
// 输入:
//[
//['1','1','1','1','0'],
//['1','1','0','1','0'],
//['1','1','0','0','0'],
//['0','0','0','0','0']
//]
//输出: 1
//
//
// 示例 2:
//
// 输入:
//[
//['1','1','0','0','0'],
//['1','1','0','0','0'],
//['0','0','1','0','0'],
//['0','0','0','1','1']
//]
//输出: 3
//解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
//
// Related Topics 深度优先搜索 广度优先搜索 并查集
// 👍 784 👎 0
package leetcode.editor.cn;
/**
* [200]岛屿数量
*/
public class NumberOfIslands {
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int numIslands(char[][] grid) {
if(grid.length == 0 || grid[0].length == 0)
return 0;
int n = grid.length;
int m = grid[0].length;
UnionFind unionFind = new UnionFind(grid);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(grid[i][j] == '1') {
int parent = i * m + j;
if(i > 0 && grid[i - 1][j] == '1')
unionFind.union(parent, (i - 1) * m + j);
if(i < n - 1 && grid[i + 1][j] == '1')
unionFind.union(parent, (i + 1) * m + j);
if(j > 0 && grid[i][j - 1] == '1')
unionFind.union(parent, i * m + (j - 1));
if(j < m - 1 && grid[i][j + 1] == '1')
unionFind.union(parent, i * m + (j + 1));
}
}
}
return unionFind.count;
}
class UnionFind {
int count;
int[] parent;
public UnionFind(char[][] grid) {
int n = grid.length;
int m = grid[0].length;
parent = new int[n * m];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(grid[i][j] == '1') {
parent[i * m + j] = i * m + j;
count++;
}
}
}
}
public int find(int x) {
while(x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public void union(int x, int z) {
int rootX = find(x);
int rootZ = find(z);
if(rootX == rootZ) return;
parent[rootX] = rootZ;
count--;
}
}
}
//leetcode submit region end(Prohibit modification and deletion)
public static void main(String[] args) {
Solution solution = new NumberOfIslands().new Solution();
}
}