hdu 1198（再续并查集）

た入场券 2022-08-23 11:54 56阅读 0赞

/*再续并查集 hdu 1198*/
    # include<iostream>
    # include<cstdio>
    # include<cstring>
    # include<cstdlib>
    # include<cmath>
    # include<algorithm>
    using namespace std;
    const int N=58;
    char s[11][5]={"1010","1001","0110","0101",//这里用0或1来代表每块的地的上下左右方向上是否有管口，0就此方向代表无管口，1就代表有管口
                   "1100","0011","1011","1110",//个人觉得这是个好方法，好形象更容易理解，这是在一大神那学的
                   "0111","1101","1111"};
    int bin[N][N];
    char map[N][N];
    int n,m;
    int findx(int x)//压缩路径优化操作函数
    {
        if(x!=bin[x/n][x%n])
            bin[x/n][x%n]=findx(bin[x/n][x%n]);//用递归的思想
        return bin[x/n][x%n];
    }
    void merge(int x,int y)//合并集合函数
    {
        int fx,fy;
        fx=findx(x);
        fy=findx(y);
        if(fx!=fy)
            bin[fy/n][fy%n]=fx;
    }
    void judge(int i,int j)//判断是否联通函数，分别对map[i][j]上下左右是否联通
    {
        if(j>0&&s[map[i][j]-'A'][2]=='1'&&s[map[i][j-1]-'A'][3]=='1')//用ASCII码的知识，如果两个口都是1 说明都有口那么可以连通
            merge(i*n+j,i*n+j-1);//所以将这两个合并在一个集合中
        if(i>0&&s[map[i][j]-'A'][0]=='1'&&s[map[i-1][j]-'A'][1]=='1')//同理
            merge(i*n+j,(i-1)*n+j);
    }
    int main()
    {
        while(cin>>m>>n&&(m!=-1||n!=-1))
        {
    
            for(int i=0;i<m;i++)
            {
                scanf("%s",map[i]);
                for(int j=0;j<n;j++)
                {
                    bin[i][j]=i*n+j;//对父亲节点进行初始化
                }
            }
    
            for(int i=0;i<m;i++)
                for(int j=0;j<n;j++)
            {
                judge(i,j);
            }
         int count=0;
            for(int i=0;i<m;i++)
                for(int j=0;j<n;j++)
            {
                if(bin[i][j]==i*n+j)//判断没有合并的集合，并计算没合并集合的个数，每个集合就是一个连通分支数
                    count++;
            }
            cout<<count<<endl;
        }
    
        return 0;
    }
    /*
    总结体会：
    这道题有所不同是要我们自己去判断是否联通，那么他的难点也在于此，
    如何形象转化去判断是否联通，所以这里用一个个人认为很好的方法
    就是用0 1 字符来代表是否有管口。
    我相信这种类型转化在以后做题中应该有大的帮助
    */