输入：grid = [" /","/ "]
输出：2
解释：2×2网格中，两个斜杠将正方形分成两个三角形区域。

LeetCode 959. 由斜杠划分区域 题目描述 在一个 1×1 的正方形网格中，每个单元格不是用一条从左上到右下的斜杠 / 分隔，就是用一条从右上到左下的反斜杠 \ 分隔，或者是空格（即没有斜杠）。这些斜杠将单元格划分成若干区域。 题目会给你一个 n x n 的网格 grid ，其中 grid[i][j] 可以是 '/' 、 '\' 或 ' ' 。你需要返回网格被斜杠划分后形成的 区域的数量 。 示例 约束条件 n == grid.length grid[i] 长度为 n grid[i][j] 是 '/' 、 '\' 或 ' ' 解题思路 这个问题看似复杂，但可以通过 将每个单元格细分成更小的子单元格 ，然后用 并查集（Union-Find） 合并连通区域来解决。具体步骤如下： 1. 单元格细分 把一个单元格看成由 4 个小三角形（或称为“子区域”）组成，编号为 0、1、2、3： 0：左上三角形 1：右上三角形 2：左下三角形 3：右下三角形 这样，无论单元格内是 / 、 \ 还是空格，我们都可以通过合并这 4 个子区域来表示斜杠的划分。 2. 斜杠对子区域的连接影响 如果是 ' ' （空格）：单元格内 4 个子区域全部连通（即合并 0-1-2-3）。 如果是 '/' ：将左上(0)和右上(1)分开，左下(2)和右下(3)分开，但 0 与 2 连通，1 与 3 连通（即合并 0-2、1-3）。 如果是 '\' ：将左上(0)和左下(2)分开，右上(1)和右下(3)分开，但 0 与 1 连通，2 与 3 连通（即合并 0-1、2-3）。 3. 单元格之间的连通 除了单元格内部，相邻单元格的边界子区域也是连通的： 每个单元格的 右侧 ：当前单元格的 1（右上）与右边相邻单元格的 3（左下）连通。 每个单元格的 下方 ：当前单元格的 2（左下）与下边相邻单元格的 0（左上）连通。 4. 使用并查集 初始化并查集，每个子区域是一个独立节点，总节点数 = n * n * 4 。 根据上述规则合并对应的子区域。 最后统计并查集中连通分量的数量，即为区域数。 逐步详解 步骤1：建立并查集类 实现基本的 find 和 union 操作，并维护连通分量计数。 步骤2：确定索引映射 对于网格中第 (i, j) 个单元格，它的 4 个子区域编号为： index = (i * n + j) * 4 + k ，其中 k = 0,1,2,3 。 步骤3：单元格内部合并 遍历每个单元格： 空格：合并 k=0,1,2,3。 / ：合并 (0,2) 和 (1,3)。 \ ：合并 (0,1) 和 (2,3)。 步骤4：单元格间合并 遍历每个单元格： 向右合并：当前单元格的 k=1 与右边单元格的 k=3 合并。 向下合并：当前单元格的 k=2 与下边单元格的 k=0 合并。 步骤5：统计连通分量 遍历所有子区域节点，通过并查集 find 找根节点，用集合记录不同根的数量，即为区域数。 举例说明 以 grid = [" /","/ "] （n=2）为例： 单元格 (0,0) ：字符为 ' ' ，合并其四个子区域 (0,1,2,3)。 单元格 (0,1) ：字符为 '/' ，合并 (0,2) 和 (1,3)。 单元格 (1,0) ：字符为 '/' ，合并 (0,2) 和 (1,3)。 单元格 (1,1) ：字符为 ' ' ，合并其四个子区域 (0,1,2,3)。 横向相邻合并 ： (0,0)的1 与 (0,1)的3 合并 (1,0)的1 与 (1,1)的3 合并 纵向相邻合并 ： (0,0)的2 与 (1,0)的0 合并 (0,1)的2 与 (1,1)的0 合并 最终并查集会形成 2 个连通分量，因此区域数为 2。 时间复杂度 每个单元格处理常数次合并操作，并查集近似 O(α(n²))，其中 α 是反阿克曼函数，近乎常数。 总时间复杂度：O(n²)，空间复杂度 O(n²)。 这种方法巧妙地将斜杠划分问题转化为标准的连通分量计数问题，通过细分和并查集高效解决。