标签: 深度优先搜索 广度优先搜索 并查集 数组 哈希表 矩阵
难度: Medium
在由 1 x 1 方格组成的 n x n 网格 grid 中，每个 1 x 1 方块由 '/'、'\' 或空格构成。这些字符会将方块划分为一些共边的区域。
给定网格 grid 表示为一个字符串数组，返回 区域的数量 。
请注意，反斜杠字符是转义的，因此 '\' 用 '\\' 表示。
示例 1：
输入：grid = [" /","/ "] 输出：2
示例 2：
输入：grid = [" /"," "] 输出：1
示例 3：
输入：grid = ["/\\","\\/"] 输出：5 解释：回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。
提示：
n == grid.length == grid[i].length1 <= n <= 30grid[i][j] 是 '/'、'\'、或 ' '运行时间: 53 ms
内存: 16.2 MB
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
n = len(grid)
num_points = (n+1) * (n+1)
uf = WeightedUnionFindWithCompressedPath(num_points)
for i in range(n):
uf.union(i, i+1)
for i in range(n):
uf.union(n*(n+1)+i, n*(n+1)+i+1)
for j in range(n):
uf.union((n+1)*j, (n+1)*(j+1))
for j in range(n):
uf.union((n+1)*j + n, (n+1)*(j+1) + n)
num_area = 1
for i in range(n):
for j in range(n):
if grid[i][j] == " ":
continue
# [i, j] --- [i, j+1]
# | |
# [i+1,j] --- [i+1, j+1]
if grid[i][j] == "/":
p1 = i * (n+1) + j + 1
p2 = (i+1) * (n+1) + j
else:
p1 = i * (n+1) + j
p2 = (i+1) * (n+1) + j + 1
if uf.connected(p1, p2):
num_area += 1
continue
uf.union(p1, p2)
return num_area
class WeightedUnionFindWithCompressedPath(object):
def __init__(self, n):
self.parent = [i for i in range(n)]
self.size = [1 for _ in range(n)]
self.count = n
def find(self, p):
node = p
while self.parent[node] != node:
node = self.parent[node]
root = node
node = p
while self.parent[node] != node:
parent = self.parent[node]
if self.parent[node] != root:
self.parent[node] = root
self.size[parent] -= self.size[node]
node = parent
return root
def connected(self, p, q):
return self.find(p) == self.find(q)
def union(self, p, q):
root_p = self.find(p)
root_q = self.find(q)
if root_p == root_q:
return
if self.size[root_p] < self.size[root_q]:
self.parent[root_p] = root_q
self.size[root_q] += self.size[root_p]
else:
self.parent[root_q] = root_p
self.size[root_p] += self.size[root_q]
self.count -= 1
该题解使用并查集（Union Find）算法来解决问题。思路是将每个小方格的四个角视为独立的点，通过斜线将这些点连接起来。如果两个点被同一条斜线连接，则它们属于同一个区域。为了处理边界情况，将网格的四条边界也视为被连接起来的。遍历整个网格，根据斜线的位置将点进行合并，如果发现两个点已经在同一个集合中，则说明形成了一个新的区域。
时间复杂度: O(n^2α(n))
空间复杂度: O(n^2)
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
n = len(grid)
num_points = (n+1) * (n+1)
uf = WeightedUnionFindWithCompressedPath(num_points)
# Connect the edges of the grid
for i in range(n):
uf.union(i, i+1)
for i in range(n):
uf.union(n*(n+1)+i, n*(n+1)+i+1)
for j in range(n):
uf.union((n+1)*j, (n+1)*(j+1))
for j in range(n):
uf.union((n+1)*j + n, (n+1)*(j+1) + n)
num_area = 1
for i in range(n):
for j in range(n):
if grid[i][j] == ' ':
continue
# Determine the points to be connected based on the slash
if grid[i][j] == '/':
p1 = i * (n+1) + j + 1
p2 = (i+1) * (n+1) + j
else:
p1 = i * (n+1) + j
p2 = (i+1) * (n+1) + j + 1
# If the points are already connected, a new area is formed
if uf.connected(p1, p2):
num_area += 1
continue
uf.union(p1, p2)
return num_area
class WeightedUnionFindWithCompressedPath(object):
def __init__(self, n):
self.parent = [i for i in range(n)]
self.size = [1 for _ in range(n)]
self.count = n
def find(self, p):
# Path compression
node = p
while self.parent[node] != node:
node = self.parent[node]
root = node
node = p
while self.parent[node] != node:
parent = self.parent[node]
if self.parent[node] != root:
self.parent[node] = root
self.size[parent] -= self.size[node]
node = parent
return root
def connected(self, p, q):
return self.find(p) == self.find(q)
def union(self, p, q):
root_p = self.find(p)
root_q = self.find(q)
if root_p == root_q:
return
# Weighted union
if self.size[root_p] < self.size[root_q]:
self.parent[root_p] = root_q
self.size[root_q] += self.size[root_p]
else:
self.parent[root_q] = root_p
self.size[root_p] += self.size[root_q]
self.count -= 1
在这个问题中，每个小方格被视为由其四个角（左上、右上、左下、右下）组成的独立单元。将这些角视为独立点可以帮助我们更准确地模拟斜线如何将空间分割成不同的区域。斜线连接了某两个角点，将这两个点视为相连的一部分。这种处理方式允许我们使用并查集数据结构来有效地管理和查找哪些点是通过斜线直接或间接相连的。具体来说，通过这种方式，每次插入斜线时，我们只需考虑连接或合并两个角点的集合，这样可以简化问题的空间和逻辑复杂度，使得问题变得更易解决。
路径压缩是并查集优化技术中的一种。在执行 find 操作时，路径压缩技术确保每个节点直接指向其根节点。这是通过在 find 函数中，当我们递归地查找一个节点的根节点时，将该节点及其所有祖先节点直接链接到根节点上实现的。在代码中，每次我们查找节点的根时，我们遍历该节点到根节点的路径，并更新路径上所有节点的父节点为根节点。这种方法显著减少了查找根节点的时间，因此在执行多次 union 和 connected 操作时，可以大幅提高并查集的效率。整体上，路径压缩将 find 操作的平摊时间复杂度降低到接近 O(1)，极大地提高了数据结构的性能。
在题解中，检测两个点是否在同一个集合中是通过并查集的 connected 方法实现的。当我们尝试通过斜线连接网格中两个角点时，首先使用 connected 方法检查这两个点是否已经属于同一个集合。如果是，这意味着在连接这两个点之前，它们已经通过其他路径被连接，因此连接这两个点将会形成一个封闭区域，即形成一个新的区域。代码中对此情况的处理是，如果 connected 方法返回 true，表示这两个点已经连接，我们就将区域数量 num_area 增加 1。然后继续执行后续的连接操作，或者遍历其他的斜线。这样能确保我们正确计算了由斜线引起的所有区域的数量。