- 标签：深度优先搜索、广度优先搜索、并查集、图
- 难度：中等
题目大意
#
在由 1 * 1 方格组成的 n * n 网格 grid 中，每个 1 * 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。
注意：反斜杠字符是转义的，因此 \ 用 \\ 表示。
现在给定代表网格的二维数组 grid，要求：返回区域的数目。
解题思路
#
我们把一个 1 * 1 的单元格分割成逻辑上的 4 个部分，则 空格、/、\\ 可以将 1 * 1 的方格分割为以下三种形态：
在进行遍历的时候，需要将联通的部分进行合并，并统计出联通的块数。这就需要用到了并查集。
遍历二维数组 gird，然后在「单元格内」和「单元格间」进行合并。
现在我们为单元格的每个小三角部分按顺时针方向都编上编号，起始位置为左边。然后单元格间的编号按照从左到右，从上到下的位置进行编号，如下图所示：
假设当前单元格的起始位置为 index，则合并策略如下：
- 如果是单元格内：
- 如果是空格：合并
index、index + 1、index + 2、index + 3。
- 如果是
/：合并 index 和 index + 1，合并 index + 2 和 index + 3。
- 如果是
\\：合并 index 和 index + 3，合并 index + 1 和 index + 2。
- 如果是单元格间，则向下向右进行合并：
- 向下：合并
index + 3 和 index + 4 * size + 1 。
- 向右：合并
index + 2 和 index + 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.count = n
def find(self, x):
while x != self.parent[x]:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return
self.parent[root_x] = root_y
self.count -= 1
def is_connected(self, x, y):
return self.find(x) == self.find(y)
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
size = len(grid)
m = 4 * size * size
union_find = UnionFind(m)
for i in range(size):
for j in range(size):
index = 4 * (i * size + j)
ch = grid[i][j]
if ch == '/':
union_find.union(index, index + 1)
union_find.union(index + 2, index + 3)
elif ch == '\\':
union_find.union(index, index + 3)
union_find.union(index + 1, index + 2)
else:
union_find.union(index, index + 1)
union_find.union(index + 1, index + 2)
union_find.union(index + 2, index + 3)
if j + 1 < size:
union_find.union(index + 2, index + 4)
if i + 1 < size:
union_find.union(index + 3, index + 4 * size + 1)
return union_find.count
|