HDU 1198(并查集;dfs)

深碍√TFBOYSˉ_ 2022-09-20 11:25 182阅读 0赞

题意：给出a-k个图形，求由这些图形拼凑起来的图中的管道一共有几个连通管道。

并查集：

#include<stdio.h>
    #include<string.h>
    //
    char str[2][9]={
       {"ABEGHJK"},{"ACFGHIK"}};
    int f[2505],m,n;
    char map[52][52];
    
    int check(int x,int y)
    {
        if(x>=0 && x<m && y>=0 && y<n)return 1;
        return 0;
    }
    
    int getFather(int a)
    {
        while(a!=f[a])a=f[a];
        return a;
    }
    /** 合并两个集合 */
    void Union(int a,int b)
    {
        int root1=getFather(a);
        int root2=getFather(b);
        if(root1!=root2)
        {
            if(root1<root2)f[root2]=root1;
            else f[root1]=root2;
        }
    }
    /** 
    * 判断两个型号的水管是否可以连在一起 
    */
    int judge(char c,int flag)
    {
        int i;
        for(i=0;i<7;i++)
        {
            if(str[flag][i]==c)return i+1;
        }
        return 0;
    }
    void process()
    {
        int i,j,dx,dy;
        char c;
        for(i=0;i<=n*m;i++)f[i]=i;
        for(i=0;i<m;i++)
        {
            for(j=0;j<n;j++)
            {
            
                c=map[i][j];
                //判断下方，当前区域的类型是除A,B,F,G以外的。
                if(c=='C' || c=='D' || c=='E' || c=='H'
                    || c=='I' || c=='J' || c=='K')
                {
                    dx = i+1;
                    dy = j;
                    if(check(dx,dy))
                    {
                        //下方区域是否是 A,B,E,G,H,J,K之一
                        if(judge(map[dx][dy],0))
                        {
                            //合并两个区域
                            Union(i*n+j,dx*n+dy);
                        }
                    }
                }
                //判断右方
                if(c=='B' || c=='D' || c=='F' || c=='G'
                    || c=='I' || c=='J' || c=='K')
                {
                    dx=i;
                    dy=j+1;
                    if(check(dx,dy))
                    {
                        //右方区域是否是A,C,F,G,H,I,K之一
                        if(judge(map[dx][dy],1))
                        {
                            Union(i*n+j,dx*n+dy);
                        }
                    }
                }
            }
        }
        int result=0;
        for(i=0;i<n*m;i++)if(f[i]==i)result++;
        printf("%d\n",result);
    }
    int main()
    {
        int i;
        while(scanf("%d%d",&m,&n))
        {
            if(m<0 || n<0)break;
            for(i=0;i<m;i++)scanf("%s",map[i]);
            process();
        }
        return 0;
    }

dfs:

#include<iostream>
    using namespace std;
    int n,m;
    char pipe[55][55];
    int dir[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    int a[11][4]={
       {1,0,1,0},{1,0,0,1},{0,1,1,0},{0,1,0,1},
    {1,1,0,0},{0,0,1,1},{1,0,1,1},{1,1,1,0},{0,1,1,1},
    {1,1,0,1},{1,1,1,1}};//重点，标记每个pipe上下左右的状态
    void DFS(int x,int y)
    {
        int i,xx,yy;
        char ch1;
        ch1=pipe[x][y];
        pipe[x][y]=NULL;
        for(i=0;i<4;i++)
        {
            xx=x+dir[i][0];
            yy=y+dir[i][1];
            if(xx<0||yy<0||xx>=n||yy>=m)
            continue;
            if(i==0||i==1)
            {
                if(a[ch1-65][i]&&pipe[xx][yy]!=NULL&&a[pipe[xx][yy]-65][!i])
                DFS(xx,yy);
            }
            else
            if(a[ch1-65][i]&&pipe[xx][yy]!=NULL&&a[pipe[xx][yy]-65][!(i-2)+2])
            DFS(xx,yy);
        }
    }
    int main()
    {
        int i,j;
        int count;
        while(cin>>n>>m,n>0||m>0)
        {
            for(i=0;i<n;i++)
            for(j=0;j<m;j++)
            cin>>pipe[i][j];
            count=0;
            for(i=0;i<n;i++)
            {
                for(j=0;j<m;j++)
                {
                    if(pipe[i][j]!=NULL)
                    {
                        DFS(i,j);
    count++;
                    }
                }
            }
            cout<<count<<endl;
        }
        return 0;
    }