在由 1x1 方格组成的 n x n 网格中，每个方格由 ‘/‘、’' 或空格划分。返回区域数量。
示例 1:
输入：grid = [“ /“,”/ “]
输出：2
示例 2:
输入：grid = [“ /“,” “]
输出：1
提示:
- n == grid.length == grid[i].length
- 1 <= n <= 30
- grid[i][j] 是 ‘/‘、’' 或 ‘ ‘
解析
每个格子划分为 4 个三角形区域，使用并查集将相邻区域合并。
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
| var regionsBetweenSlashes = function (grid) {
const n = grid.length;
const parent = Array(n * n * 4).fill(0).map((_, i) => i);
const find = (x) => parent[x] === x ? x : (parent[x] = find(parent[x]));
const union = (a, b) => {
const ra = find(a), rb = find(b);
if (ra !== rb) parent[ra] = rb;
};
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
const root = (i * n + j) * 4;
if (grid[i][j] === ' ') {
union(root, root + 1);
union(root, root + 2);
union(root, root + 3);
} else if (grid[i][j] === '/') {
union(root, root + 1);
union(root + 2, root + 3);
} else {
union(root, root + 3);
union(root + 1, root + 2);
}
if (i < n - 1) union(root + 2, ((i + 1) * n + j) * 4);
if (j < n - 1) union(root + 1, (i * n + j + 1) * 4 + 3);
}
}
const regionSet = new Set();
for (let i = 0; i < parent.length; i++) regionSet.add(find(i));
return regionSet.size;
};
|
时间复杂度 O(N^2 * α(N))，空间复杂度 O(N^2)。