想了一下怎么定义union-find的node
我是笨笨的
想到先把一个block切成四分 因为我也不知道哪里会是\哪里会是/
大概像这样编排
https://i.imgur.com/fzFpHwv.png (n=2)
第一次union find先把虚线部分给union起来
每个block跟右与下的block做，加上boundary check
第二次union find再去做题目给的slash部分
" "的话就(0,1,2,3)union起来
"\"的话就(0,1) (2,3)各自union
"/"的话就(0,3) (1,2)各自union
第一次union那边boundary check写的有点丑就是了
应该可以更简单==
好久没用C++了
最近来回锅一下好了
class Solution {
public:
int unionfind(vector<int>& parent, int n1, int n2){
int r1 = parent[n1];
while (r1 != parent[r1]) {
r1 = parent[r1];
}
int r2 = parent[n2];
while (r2 != parent[r2]) {
r2 = parent[r2];
}
if(r2 != r1) {
parent[r2] = r1;
return 1;
}
else {
return 0;
}
}
int regionsBySlashes(vector<string>& grid) {
int n = grid.size();
int len = n*n*4;
int ans = len;
vector<int> parent(len);
// init
for(int i=0; i<len; i++) {
parent[i] = i;
}
// union find 1
for(int i=0; i<len; i+=4){
// check right
if (((i/4)+1)%n != 0) {
ans -= unionfind(parent, i+1, i+7);
}
// check bottom
if ((i+4*n) < len) {
ans -= unionfind(parent, i+2, i+4*n);
}
}
// union find 2
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++){
int idx = 4*(i*n+j);
if (grid[i][j] == ' ') {
ans -= unionfind(parent, idx, idx+1);
ans -= unionfind(parent, idx, idx+2);
ans -= unionfind(parent, idx, idx+3);
}
else if (grid[i][j] == '\\') {
ans -= unionfind(parent, idx, idx+1);
ans -= unionfind(parent, idx+2, idx+3);
}
else if (grid[i][j] == '/') {
ans -= unionfind(parent, idx, idx+3);
ans -= unionfind(parent, idx+1, idx+2);
}
}
}
return ans;
}
};