LeetCode 959. Regions Cut By Slashes

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class UF {
public:
    vector<int> f;
    vector<int> size;
    int setCount; // count of current connected components
    UF(int n): setCount(n), f(n), size(n, 1) {
        iota(f.begin(), f.end(), 0);
    }
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    void _union(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            if (size[fx] < size[fy])
                swap(fx, fy);
            f[fy] = fx;
            size[fx] += size[fy];
            --setCount;
        }
    }
};
class Solution {
public:
    int regionsBySlashes(vector<string>& grid) {
        const int n = grid.size();
        UF uf(n * n * 4); // east 0, south 1, west 2, north 3
        for (int r = 0; r < n; ++r)
            for (int c = 0; c < n; ++c) {
                int idx = r * n + c;
                int easternIndex = idx * 4;
                if (r < n - 1) {
                    int bottom = idx + n;
                    uf._union(easternIndex + 1, bottom * 4 + 3);
                }
                if (c < n - 1) {
                    int right = idx + 1;
                    uf._union(easternIndex, right * 4 + 2);
                }
                if (grid[r][c] == '/') {
                    uf._union(easternIndex, easternIndex + 1);
                    uf._union(easternIndex + 2, easternIndex + 3);
                } else if (grid[r][c] == '\\') {
                    uf._union(easternIndex, easternIndex + 3);
                    uf._union(easternIndex + 1, easternIndex + 2);
                } else {
                    uf._union(easternIndex, easternIndex + 1);
                    uf._union(easternIndex + 1, easternIndex + 2);
                    uf._union(easternIndex + 2, easternIndex + 3);
                }
            }
        return uf.setCount;
    }
};