Leetcode 959：由斜杠划分区域（超详细的解法！！！）

在由 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] 是 '/'、'\'、或 ' '。

解题思路

这个问题非常有意思，这实际是一个岛屿个数的问题，所以不难想到通过DFS来做。

这里我们使用3×3个像素表示一个最小单元最为合适。

class Solution:
    def regionsBySlashes(self, grid):
        """
        :type grid: List[str]
        :rtype: int
        """
        grid_len = len(grid)
        g_len = grid_len*3
        g = [[0]*g_len for _ in range(g_len)]
        def dfs(g, i, j):
            if i >= 0 and j >= 0 and i < g_len and j < g_len and g[i][j] == 0:
                g[i][j] = 1
                dfs(g, i - 1, j)
                dfs(g, i + 1, j)
                dfs(g, i, j - 1)
                dfs(g, i, j + 1)
            
        for i in range(grid_len):
            for j in range(grid_len):
                if grid[i][j] == '/':
                    g[i*3+2][j*3], g[i*3+1][j*3+1], g[i*3][j*3+2] = 1, 1, 1
                if grid[i][j] == '\\':
                    g[i*3][j*3], g[i*3+1][j*3+1], g[i*3+2][j*3+2] = 1, 1, 1
                    
        res = 0
        for i in range(g_len):
            for j in range(g_len):
                if g[i][j] == 0:
                    dfs(g, i, j)
                    res += 1
                
        return res

我们也可以参考Leetcode 947：移除最多的同行或同列石头（超详细的解法！！！）采用并查集来做。

我们可以通过/和\将一个区域划分为四块，然后我们按照顺时针自顶开始的顺序标记划分后的区域为1、2、3和4。我们此时就可以开始遍历输入的grid，

如果碰到'/'，我们就将0和3进行归并。如果碰到'\\'，我们就将1和2归并。如果碰到' '，我们就将1、2、3和4全部归并。对于更加复杂的例子，如例5

我们首先碰到'/'，所以我们就将第一个方格中的03和12分别归并。

同理接着将后面碰到的'/'和' '一次归并。

最后我们将横向第二个小方格中的0和第一个小方格中的2归并，将纵向第二个小方格中的3和第一个小方格中的1归并，这样我们就把中间这个部分归并为了一个集合。对于下方的三角形区域做同样的操作。

class Solution:
    def regionsBySlashes(self, grid):
        """
        :type grid: List[str]
        :rtype: int
        """
        s = dict()
        
        def find(x):
            s.setdefault(x, x)
            if s[x] != x:
                s[x] = find(s[x])
                
            return s[x]
        
        def union(x, y):
            s[find(x)] = find(y)
            
        grid_len = len(grid)
        for i in range(grid_len):
            for j in range(grid_len):
                if i:
                    union((i, j, 0), (i-1, j, 2))
                if j:
                    union((i, j, 3), (i, j-1, 1))
                if grid[i][j] != '/':
                    union((i, j, 0), (i, j, 1))
                    union((i, j, 3), (i, j, 2))
                if grid[i][j] != '\\':
                    union((i, j, 0), (i, j, 3))
                    union((i, j, 2), (i, j, 1))
                    
        return len(set(map(find, s)))

reference:

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

https://leetcode.com/problems/regions-cut-by-slashes/discuss/205674/C%2B%2B-with-picture-DFS-on-upscaled-grid

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！

Leetcode 959：由斜杠划分区域（超详细的解法！！！）

相关推荐