959. Regions Cut By Slashes
题目:
给你一个由字串组成的vector，假设长度为n，其中grid[i]代表对一个由n*n个1*1的
square的i-th row的切割法，每个小square可能切割法有"/" ，"\"，" "(不切割)三种
求出这个大square经过这些小square的切割后的region数
思路:
概念就是把"/" "\"这两种分割代表成相邻两点没有连结，然后求出compoment数，所以
用BFS DFS或是union find都可以解决问题，使用union find的话，概念上就是把任一个
小的1*1 square切成两份当读到两种分割法时根据当前所在位置这两个部分可以分别对上
或是左做union，如果是无分割，则将两个部分union后一样根据位置可以分别对上或左做
union，但须注意的是因为这样我们每次都是把已造访过的node union到新造访node下，
所以并没有真的用到path comprassion，所以最后判断size时要对每一个点做一次find
才能得到正解，所以感觉如果是改成每次对未造访的下和右边的node做union并加上
union by rank结果才是最佳的?
int fin_d(int cur,vector<int> &ro_list){
if(ro_list[cur]!=cur){
ro_list[cur]=fin_d(ro_list[cur],ro_list);
}
return ro_list[cur];
}
void un_ion(int cur,int tar,vector<int> &ro_list){
ro_list[fin_d(cur,ro_list)]=fin_d(tar,ro_list);
}
int regionsBySlashes(vector<string>& grid) {
int n=grid.size();
vector<int> parent(2*n*n+1,-1);
for(int i=1;i<parent.size();++i){
parent[i]=i;
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(grid[i][j]==' '){
un_ion((i*(2*n)+2*j+1),(i*(2*n)+2*j+2),parent);
if(i>0){
if(grid[i-1][j]=='/'){
un_ion((i*(2*n)+2*j+1),((i-1)*(2*n)+2*j+2),parent);
}
else{
un_ion((i*(2*n)+2*j+1),((i-1)*(2*n)+2*j+1),parent);
}
}
if(j>0){
un_ion((i*(2*n)+2*j),(i*(2*n)+2*j+1),parent);
}
}
else if(grid[i][j]=='/'){
if(i>0){
if(grid[i-1][j]=='/'){
un_ion((i*(2*n)+2*j+1),((i-1)*(2*n)+2*j+2),parent);
}
else{
un_ion((i*(2*n)+2*j+1),((i-1)*(2*n)+2*j+1),parent);
}
}
if(j>0){
un_ion((i*(2*n)+2*j+1),((i)*(2*n)+2*j),parent);
}
}
else{
//means grid[i][j]=='\'
if(i>0){
if(grid[i-1][j]=='/'){
un_ion((i*(2*n)+2*j+2),((i-1)*(2*n)+2*j+2),parent);
}
else{
un_ion((i*(2*n)+2*j+2),((i-1)*(2*n)+2*j+1),parent);
}
}
if(j>0){
un_ion((i*(2*n)+2*j+1),((i)*(2*n)+2*j),parent);
}
}
}
}
unordered_set<int> ans;
for(int i=1;i<parent.size();++i){
ans.insert(fin_d(parent[i],parent));
}
return ans.size();
}