/
RegionsCutBySlashes.java
112 lines (94 loc) · 3.41 KB
/
RegionsCutBySlashes.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
106
107
108
109
110
111
112
// https://leetcode.com/problems/regions-cut-by-slashes
class Solution {
public int regionsBySlashes(String[] grid) {
// We consider each points in corner of each element as dots
// So a setup of
// [' ', ' ']
// [' ', ' ']
// looks like
// . . .
// . . .
// . . .
// (As it is difficult to represent the slashes in dot diagram)
// A slash connects 2 dots
// Edges are connected
// Question now becomes to find the no. of cycles in the graph
int n = grid.length;
int dots = n + 1;
UnionFind uf = new UnionFind(dots * dots);
// Connect the edges
for (int i = 0; i < dots; i++) {
for (int j = 0; j < dots; j++) {
if (i == 0 || i == dots - 1 || j == 0 || j == dots - 1) {
int cell = i * dots + j;
// We assume that the root of the edges is [0, 0] whose cell value
// is 0.
if (cell != 0) {
uf.union(0, cell);
}
}
}
}
// Now we examine the slashes and union them
// We union them from bottom (2nd arg of union) to top (1st arg).
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
char c = grid[i].charAt(j);
if (c == '/') {
// Bottom left = (i + 1, j)
int bottomLeft = (i + 1) * dots + j;
// Top right = (i, j + 1)
int topRight = i * dots + j + 1;
// Union
uf.union(topRight, bottomLeft);
} else if (c == '\\') {
// Top left = (i, j)
int topLeft = i * dots + j;
// Bottom right = (i + 1, j + 1)
int bottomRight = (i + 1) * dots + j + 1;
// Union
uf.union(topLeft, bottomRight);
}
}
}
return uf.regions;
}
class UnionFind {
int[] root;
int[] rank;
int regions;
public UnionFind(int n) {
root = new int[n];
rank = new int[n];
regions = 1;
for (int i = 0; i < n; i++) {
root[i] = i;
rank[i] = 0;
}
}
int find(int x) {
if (x == root[x]) {
return x;
}
return root[x] = find(root[x]);
}
void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
root[rootX] = rootY;
} else if (rank[rootY] < rank[rootY]) {
root[rootY] = rootX;
} else {
root[rootX] = rootY;
rank[rootY] += 1;
}
} else {
// This is very interesting
// If this condition is true, and x != y, then a cycle is present in the graph
regions += 1;
}
}
}
}