Hdu 1198 Farm Irrigation (DFS 异或的应用)

男娘i 2022-09-20 15:09 98阅读 0赞

参考了：http://blog.csdn.net/firwaless/article/details/18672239

题意：有一块n\*m的农田，被分隔成许多小的正方形，每个正方形中都装有水管，一共有11种水管，分别用字母A~K标明。正方形的中心可以有水源，水可以沿着水管流到其他的正方形上，问至少需要多少个水源，保证农田全部被灌溉。

本题也可以用并查集。参考的原文判断相反方向的异或用的很精髓，学习了。

#include <cstdio>
    #include <cstring>
    
    const int N=55;
    int dx[4]={-1,1,0,0}; //注意顺序,上下左右
    int dy[4]={0,0,-1,1};
    int n,m;
    
    //A~K 每个水管在上下左右四个方向上是否有开口
    bool rel[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};
    
    char g[N][N];
    bool visit[N][N];
    
    bool OK (int x,int y)
    {
        return visit[x][y]==false && x>=0 && x<n && y>=0 && y<m;
    }
    
    void DFS (int x, int y)
    {
        visit[x][y]=true;
        for (int i=0;i<4;i++)
        {
            int a=x+dx[i];
            int b=y+dy[i];
            /*判断水管的当前方向和要搜索的下一个水管的相反方向是否连通 */
            if (OK(a,b) && rel[g[x][y]-'A'][i] && rel[g[a][b]-'A'][i ^ 1]) //利用了异或
                DFS(a,b);
        }
    }
    
    int main ()
    {
        while (scanf("%d%d", &n, &m),n!=-1)
        {
            int i,cnt=0;
            for (i=0;i<n;i++)
                scanf("%s",g[i]);
            memset(visit,false,sizeof(visit));
            for (i=0;i<n;i++) for (int j=0;j<m;j++)
                if (visit[i][j]==false)
                {
                    cnt++;
                    DFS(i,j);
                }
            printf("%d\n",cnt);
        }
        return 0;
    }