959. Regions Cut By Slashes
第一感就是切成四塊做 union find
可是感覺寫起來挺瑣碎的 覺得medium有這麼搞剛嗎
但想了一下也沒想到比較漂亮的解法
實際寫起來行數很多 不過蠻直觀的 把該合併的合併就ok了
```
struct UnionFind {
int count;
vector<int> parent, rank;
UnionFind(int n) {
parent = vector<int>(n);
rank = vector<int>(n);
iota(parent.begin(), parent.end(), 0);
count = n;
}
int find(int x) {
if (parent[x] == x) return x;
return (parent[x] = find(parent[x]));
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (rank[x] < rank[y])
swap(x, y);
parent[y] = x;
count -= 1;
}
};
class Solution {
public:
int regionsBySlashes(vector<string>& grid) {
/*
* \ 0 /
* \ /
* 1 X 2
* / \
* / 3 \
*/
int n = grid.size();
auto get = [=](int r, int c) {
return (r * n + c) * 4;
};
int total = n * n * 4;
UnionFind uf(total);
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
int base = get(r, c);
int up = get(r - 1, c) + 3;
int left = get(r, c - 1) + 2;
if (r > 0) uf.merge(base, up);
if (c > 0) uf.merge(base + 1, left);
if (grid[r][c] == ' ') {
uf.merge(base, base + 1);
uf.merge(base, base + 2);
uf.merge(base, base + 3);
} else if (grid[r][c] == '/') {
uf.merge(base, base + 1);
uf.merge(base + 2, base + 3);
} else if (grid[r][c] == '\\') {
uf.merge(base, base + 2);
uf.merge(base + 1, base + 3);
} else {
std::unreachable();
}
}
}
return uf.count;
}
};
```