题目描述

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

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

返回区域的数目。

样例

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

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

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

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

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

注意

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

算法

(并查集) $O(n^2 \alpha(n))$

1. 首先把每个大格子再拆成四个小格子，（按顺时针）顺序编号(0, 1, 2, 3)，这样总共有 $4n^2$ 个小格子。
2. 每个大格子中，连接某个小格子 (1) 到其右侧大格子的某个小格子 (3)，(2) 到其下侧小格子 (0)。
3. 然后根据 grid 数组中斜线的划分情况，在每个大格子内部连接小格子。
4. 用并查集可以求出总共有多少个连通块。

时间复杂度

• 建图的时间复杂度为 $O(n^2)$，并查集操作的时间复杂度为 $O(\alpha(n))$，故总时间复杂度为 $O(n^2 \alpha(n))$。

C++ 代码

class Solution {
public:

    vector<int> f, sz;

    int find(int x) {
        return x != f[x] ? f[x] = find(f[x]) : x;
    }

    void uni(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            if (sz[fx] < sz[fy]) {
                f[fx] = fy;
                sz[fy] += sz[fx];
            }
            else {
                f[fy] = fx;
                sz[fx] += sz[fy];
            }
        }
    }

    int regionsBySlashes(vector<string>& grid) {
        int n = grid.size();

        f = vector<int>(4 * n * n);
        sz = vector<int>(4 * n * n);

        for (int i = 0; i < 4 * n * n; i++) {
            f[i] = i;
            sz[i] = 1;
        }

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n - 1; j++) {
                int x = 4 * (i * n + j) + 1, y = 4 * (i * n + j + 1) + 3;
                uni(x, y);
            }

        for (int j = 0; j < n; j++)
            for (int i = 0; i < n - 1; i++) {
                int x = 4 * (i * n + j) + 2, y = 4 * ((i + 1) * n + j);
                uni(x, y);
            }

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                int x = 4 * (i * n + j);
                if (grid[i][j] == ' ') {
                    uni(x, x + 1);
                    uni(x + 1, x + 2);
                    uni(x + 2, x + 3);
                }
                else if (grid[i][j] == '/') {
                    uni(x, x + 3);
                    uni(x + 1, x + 2);
                }
                else {
                    uni(x, x + 1);
                    uni(x + 2, x + 3);
                }
            }

        int ans = 0;
        for (int i = 0; i < 4 * n * n; i++)
            if (i == find(i))
                ans++;

        return ans;
    }
};