JZX轻语：简
LeetCode 959 - 由斜杠划分区域
发表于2024年05月29日
这种二维空间融合/扩展+求解划分数量的问题，可以考虑使用并查集的方式~我们可以将第i行第j列的格子编号为n * i + j，然后将每个格子等分为”左右”两部分，其中第i行第j列左右两部分编号为2 * (n * i + j)及2 * (n * i + j) + 1。这样，我们可以根据每个格子的划分形式，将左右两部分与其相邻格子的左右两部分进行合并，最终得到的连通分量即为答案。
划分的规则如下：
每个格子的左部分可以和左边格子（如果有）相合并，无论当前格子的划分形式如何
如果格子没有划分（空格），则该格子的左右两个部分合并
如果格子划分为
/或者没有划分，则左部分和上面格子（如果有）的朝下部分（所谓朝下部分，即如果划分为/，则为右部分（即处于右下角）；如果为/，则为左部分（即处于左下角））合并如果格子划分为
\或者没有划分，则右部分和上面格子（如果有）的朝下部分合并；
class UnionSet:
def __init__(self, n: int):
self.pa = list(range(n))
self.l = n
def find(self, u: int) -> int:
if self.pa[u] != u:
self.pa[u] = self.find(self.pa[u])
return self.pa[u]
def unite(self, u: int, v: int):
up, vp = self.find(u), self.find(v)
if up == vp:
return
self.pa[up] = vp
self.l -= 1
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
n = len(grid)
uset = UnionSet(n * n * 2)
for i in range(n):
for j in range(n):
square = i * n + j
l = square * 2
r = square * 2 + 1
if grid[i][j] == ' ':
uset.unite(l, r)
if j > 0:
uset.unite(l - 1, l)
if i > 0:
top = (square - n) * 2 if grid[i - 1][j] == '\\' else (square - n) * 2 + 1
if grid[i][j] == ' ' or grid[i][j] == '\\':
uset.unite(r, top)
if grid[i][j] == ' ' or grid[i][j] == '/':
uset.unite(l, top)
return uset.l