发表于 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

• LC 题目链接