难度：★★★☆☆
类型：几何
方法：并查集

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

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

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

返回区域的数目。

示例 1：

输入：
[
" /",
"/ "
]
输出：2

示例 2：

输入：
[
" /",
" "
]
输出：1

示例 3：

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

示例 4：

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

示例 5：

输入：
[
"//",
"/ "
]
输出：3

提示：

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

解答

这个问题看上去很复杂，但实际上是一个统计连通域个数的问题，这类问题，可以用并查集来方便的解决。

分析题目，对于每个方格，无非三种划分方式，分别用三个符号表示：
“/”：左斜杠，把一个方格分成了左上区域和右下区域两个等腰直角三角形；
“\”：右斜杠，把一个方格分成了左下区域和右下区域两个等腰直角三角形；
“ ”：空格，说明该方格不进行划分。

我们可以预先的把每个方格用一个叉号划分成上下左右四个区域，都是四个小的等腰直角三角形，这样，对于n×n个方格，一共就有n×n×4个预先划分好的小区域，通过合并这些区域，构建并查集并实时的统计当前区域的个数，最终实现整体区域个数的统计。

关于区域的合并，有以下几点需要注意：

1. 对于(row，column)号方格，根据三种不同的划分方式，做不同的区域合并：
   1.1 “/”：左斜杠，合并左区域和上区域，合并右区域和下区域；
   1.2 “//”：右斜杠，合并左区域和下区域，合并右区域和上区域；
   1.3 “ ”：空格，全部需要合并，将上下左右四个区域建立连接。

2. 不同方格之间的区域的合并不要忘记。
   2.1 每当遇到行标不小于1的方格，需要把该方格(row，column)的上区域和在它上面的方格(row-1，column)的下区域合并。
   2.2 每当遇到行标不小于1的方格，需要把该方格(row，column)的左区域和在它左边的方格(row，column-1)的右区域合并。

关于并查集的构建，有以下几点注意：

1. 我们用三元组来表达每个直角三角形小区域，其中包含方格所在行，列以及小区域的编号，初始化过程每个小区域的祖先结点都是自己；

2. 两个小区域的合并，可以通过将它们的祖先结点连接来实现，记得每次合并都会使连通域计数器减一，为了避免重复合并，可以预先判断两个小区域是否已经联通；

3. 祖先结点的搜寻过程，需要及时将父节点的祖先结点更新；

class UF:
    def __init__(self, objs):
        self.parent = {o: o for o in objs}
        self.cnt = len(objs)

    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)
        top, left, right, bottom = 0, 1, 2, 3   # "top", "left", "right", "bottom"
        uf = UF([(row, column, area) for row in range(n) for column in range(n) for area in [top, left, right, bottom]])

        for row in range(n):
            for column in range(n):
                v = grid[row][column]
                if row > 0:
                    uf.union((row - 1, column, bottom), (row, column, top))
                if column > 0:
                    uf.union((row, column - 1, right), (row, column, left))
                if v == '/':
                    uf.union((row, column, left), (row, column, top))
                    uf.union((row, column, right), (row, column, bottom))
                if v == '\\':
                    uf.union((row, column, top), (row, column, right))
                    uf.union((row, column, left), (row, column, bottom))
                if v == ' ':
                    uf.union((row, column, left), (row, column, top))
                    uf.union((row, column, top), (row, column, right))
                    uf.union((row, column, right), (row, column, bottom))

        return uf.cnt

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析