959. 由斜杠划分区域（并查集）

959. 由斜杠划分区域

没想到这也能并查集

class Solution {
public:
    int setcnt;
    vector<int>p;
    void init(int n){
        p.resize(4*n*n);
        setcnt=p.size();
        for(int i=0;i<p.size();i++)p[i]=i;
    }
    int find(int x){
        if(p[x]!=x)p[x]=find(p[x]);
        return p[x];
    }
    void merge(int a,int b){
        a=find(a),b=find(b);
        if(a>b) swap(a,b);
        if(a!=b) p[b]=a,setcnt--;
    }
    int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};

//   0
// 1   2
//   3   

    int regionsBySlashes(vector<string>& grid) {
        int n=grid.size();
        init(n);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int cur=(i*n+j)*4;
                char c=grid[i][j];
                
                for(int k=0;k<4;k++){
                    int a=i+dx[k],b=j+dy[k];
                    if(a>=0 && a<n && b>=0 && b<n){
                        int c2=(a*n+b)*4;
                        merge(cur+k,c2+3-k);
                    }
                }
                if(c==' ')merge(cur,cur+1),merge(cur,cur+2),merge(cur,cur+3);
                else if(c=='/')merge(cur,cur+1),merge(cur+2,cur+3);
                else if(c=='\\')merge(cur,cur+2),merge(cur+1,cur+3);
            }
        }

        return setcnt;

    }
};