- 标签:深度优先搜索、广度优先搜索、并查集、图
- 难度:中等
描述:在由 '/'
、'\'
或 ' '
构成。这些字符会将方块划分为一些共边的区域。
现在给定代表网格的二维数组
要求:返回区域的数目。
说明:
- 反斜杠字符是转义的,因此
'\'
用'\\'
表示。 -
$n == grid.length == grid[i].length$ 。 -
$1 \le n \le 30$ 。 -
$grid[i][j]$ 是'/'
、'\'
或' '
。
示例:
- 示例 1:
输入:grid = [" /","/ "]
输出:2
- 示例 2:
输入:grid = ["/\\","\\/"]
输出:5
解释:回想一下,因为 \ 字符是转义的,所以 "/\\" 表示 /\,而 "\\/" 表示 \/。
我们把一个 ' '
、'/'
、'\'
可以将
在进行遍历的时候,需要将联通的部分进行合并,并统计出联通的块数。这就需要用到了并查集。
遍历二维数组
现在我们为单元格的每个小三角部分按顺时针方向都编上编号,起始位置为左边。然后单元格间的编号按照从左到右,从上到下的位置进行编号,如下图所示:
假设当前单元格的起始位置为
- 如果是单元格内:
- 如果是空格:合并
$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$ 。
- 向下:合并
最后合并完成之后,统计并查集中连通分量个数即为答案。
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
-
时间复杂度:$O(n^2 \times \alpha(n^2))$,其中
$\alpha$ 是反Ackerman
函数。 - 空间复杂度:$O(n^2)$。