推 JIWP: 大師 08/10 12:40
→ rainkaras: 大師 08/10 12:45
推 sustainer123: 大師 08/10 12:48
推 dont: 大師 08/10 13:13
→ smart0eddie: 大師 08/10 13:22
推 oin1104: 大師 08/10 13:27
想了一下怎麼定義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;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.146.144 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723264783.A.004.html