0959. 由斜杠划分区域

题目地址 (959. 由斜杠划分区域）

https://leetcode-cn.com/problems/regions-cut-by-slashes/

题目描述

在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。

（请注意，反斜杠字符是转义的，因此 \ 用 "\\" 表示。）。

返回区域的数目。

 

示例 1：

输入：
[
  " /",
  "/ "
]
输出：2
解释：2x2 网格如下：

示例 2：

输入：
[
  " /",
  "  "
]
输出：1
解释：2x2 网格如下：

示例 3：

输入：
[
  "\\/",
  "/\\"
]
输出：4
解释：（回想一下，因为 \ 字符是转义的，所以 "\\/" 表示 \/，而 "/\\" 表示 /\。）
2x2 网格如下：

示例 4：

输入：
[
  "/\\",
  "\\/"
]
输出：5
解释：（回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。）
2x2 网格如下：

示例 5：

输入：
[
  "//",
  "/ "
]
输出：3
解释：2x2 网格如下：

 

提示：

1 <= grid.length == grid[0].length <= 30
grid[i][j] 是 '/'、'\'、或 ' '。

前置知识

• BFS

• DFS

• 并查集

公司

• 暂无

并查集

题目给了一个网格，网格有三个符号，分别是左斜杠，右斜杠和空格。我们要做的就是根据这些符号，将网格分成若干区域，并求区域的个数。

了解了题目之后，我们发现这其实就是一个求联通域个数的题目。这种题目一般有三种解法：BFS，DFS 和并查集。而如果题目需要求具体的联通信息，则需要使用 BFS 或 DFS 来完成。这里给大家提供 DFS 和并查集两种做法。

思路

使用并查集可以将网格按照如下方式进行逻辑上的划分，之所以进行如下划分的原因是一个网格最多只能被分成如下四个部分，而并查集的处理过程是合并，因此初始状态需要是一个个孤立的点，每一个点初始都是一个独立的联通区域。这在我下方代码的初始化过程有所体现。

编号方式无所谓，你可以按照你的喜好编号。不过编号方式改变了，代码要做相应微调。

这里我直接使用了不带权并查集模板 UF，没有改任何代码。

并查集模板在我的刷题插件中，插件可在我的公众号《力扣加加》回复插件获取

而一般的并查集处理信息都是一维的，本题却是二维的，如何存储？实际上很简单，我们只需要做一个简单的数学映射即可。

def get_pos(row, col):
    return row * n + col

如上代码会将原始格子 grid 的 grid[row][col] 映射到新的格子的一维坐标 row * n + col，其中 n 为列宽。而由于我们将一个格子拆成了四个，因此需要一个新的大网格来记录这些信息。而原始网格其实和旧的网格一一映射可确定，因此可以直接用原始网格，而不必新建一个新的大网格。如何做呢？其实将上面的坐标转换代码稍微修改就可以了。

def get_pos(row, col, i):
    return row * n + col + i

接下来就是并查集的部分了：

• 如果是 '/'，则将 0 和 1 合并，2 和 3 合并。

• 如果是 '\'，则将 0 和 2 合并，1 和 3 合并。

• 如果是 ' '，则将 0, 1, 2, 3 合并。

最终返回联通区域的个数即可。

需要特别注意的是当前格子可能和原始格子的上面，下面，左面和右面的格子联通。因此不能仅仅考虑上面的格子内部的联通，还需要考虑相邻的格子的联通。为了避免重复计算，我们不能考虑四个方向，而是只能考虑两个方向，这里我考虑了上面和左面。

代码

代码支持： Python3

Python Code:

class UF:
  def __init__(self, M):
      self.parent = {}
      self.cnt = 0
      # 初始化 parent，size 和 cnt
      for i in range(M):
          self.parent[i] = i
          self.cnt += 1

  def find(self, x):
      if x != self.parent[x]:
          self.parent[x] = self.find(self.parent[x])
          return self.parent[x]
      return x
  def union(self, p, q):
      if self.connected(p, q): return
      leader_p = self.find(p)
      leader_q = self.find(q)
      self.parent[leader_p] = leader_q
      self.cnt -= 1
  def connected(self, p, q):
      return self.find(p) == self.find(q)

class Solution:
    def regionsBySlashes(self, grid):
        n = len(grid)
        N = n * n * 4
        uf = UF(N)
        def get_pos(row, col, i):
            return (row * n + col) * 4 + i
        for row in range(n):
            for col in range(n):
                v = grid[row][col]
                if row > 0:
                    uf.union(get_pos(row - 1, col, 2), get_pos(row, col, 1))
                if col > 0:
                    uf.union(get_pos(row, col - 1, 3), get_pos(row, col, 0))
                if v == '/':
                    uf.union(get_pos(row, col, 0), get_pos(row, col, 1))
                    uf.union(get_pos(row, col, 2), get_pos(row, col, 3))
                if v == '\\':
                    uf.union(get_pos(row, col, 1), get_pos(row, col, 3))
                    uf.union(get_pos(row, col, 0), get_pos(row, col, 2))
                if v == ' ':
                    uf.union(get_pos(row, col, 0), get_pos(row, col, 1))
                    uf.union(get_pos(row, col, 1), get_pos(row, col, 2))
                    uf.union(get_pos(row, col, 2), get_pos(row, col, 3))

        return uf.cnt

复杂度分析

令 n 为网格的边长。

• 时间复杂度：$O(n^2)$

• 空间复杂度：$O(n^2)$

DFS

思路

要使用 DFS 在二维网格计算联通区域，我们需要对数据进行预处理。如果不明白为什么，可以看下我之前写的小岛专题。

由于题目是“/” 和 "\" 将联通区域进行了分割。因此我们可以将 “/” 和 "\" 看成是陆地，其他部分看成是水。因此我们的目标就转化为小岛问题中的求水的区域个数。

至此，我们的预处理逻辑就清楚了。就是将题目中的“/” 和 "\" 改成 1，其他空格改成 0，然后从 0 启动搜索（可以是 BFS 或者 DFS），边搜索边将水变成陆地，最终启动搜索的次数就是水的区域个数。

将 “/” 和 "\" 直接变为 1 是肯定不行的。那将 “/” 和 "\" 变成一个 2 X 2 的格子呢？也是不行的，因为无法处理上面提到的相邻格子的联通情况。

因此我们需要将 “/” 和 "\" 变成一个 3 X 3 的格子。

4 X 4 以及更多的格子也是可以的，但没有必要了，那样只会徒增时间和空间。

代码

代码支持： Python3

Python Code:

class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        m, n = len(grid), len(grid[0])
        new_grid = [[0 for _ in range(3 * n)] for _ in range(3 * m)]
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '/':
                    new_grid[3 * i][3 * j + 2] = 1
                    new_grid[3 * i + 1][3 * j + 1] = 1
                    new_grid[3 * i + 2][3 * j] = 1
                if grid[i][j] == '\\':
                    new_grid[3 * i][3 * j] = 1
                    new_grid[3 * i + 1][3 * j + 1] = 1
                    new_grid[3 * i + 2][3 * j + 2] = 1
        def dfs(i, j):
            if 0 <= i < 3 * m and 0 <= j < 3 * n and new_grid[i][j] == 0:
                new_grid[i][j] = 1
                dfs(i + 1, j)
                dfs(i - 1, j)
                dfs(i, j + 1)
                dfs(i, j - 1)
        for i in range(3 * m):
            for j in range(3 * n):
                if new_grid[i][j] == 0:
                    ans += 1
                    dfs(i, j)
        return ans

复杂度分析

令 n 为网格的边长。

• 时间复杂度：虽然我们在 $9 * m * n$ 的网格中嵌套了 dfs，但由于每个格子最多只会被处理一次，因此时间复杂度仍然是 $O(n^2)$

• 空间复杂度：主要是 new_grid 的空间，因此空间复杂度是 $O(n^2)$

扩展

这道题的 BFS 解法留给大家来完成。

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。