hdu 1198 Farm Irrigation（搜索+並查集）

/* 這個題我是用搜索過的 本來是想用並查集做，但是始終WA不得正解就直接搜索了

*/

#include<cstdio>

#include<cstring>

int n,m;
int dx[]= {0,0,1,-1},dy[]= {1,-1,0,0}; // r l d u
char s[555][555];
int p[555],vis[555][555];
struct Node
{
    int u,d,l,r;
} map[555][555];

int build(int x,int y)
{
    if(s[x][y]=='A')
    {
        map[x][y].u = 1;
        map[x][y].d = 0;
        map[x][y].l = 1;
        map[x][y].r = 0;
    }
    else if(s[x][y]=='B')
    {
        map[x][y].u = 1;
        map[x][y].d = 0;
        map[x][y].l = 0;
        map[x][y].r = 1;
    }
    else if(s[x][y]=='C')
    {
        map[x][y].u = 0;
        map[x][y].d = 1;
        map[x][y].l = 1;
        map[x][y].r = 0;
    }
    else if(s[x][y]=='D')
    {
        map[x][y].u = 0;
        map[x][y].d = 1;
        map[x][y].l = 0;
        map[x][y].r = 1;
    }
    else if(s[x][y]=='E')
    {
        map[x][y].u = 1;
        map[x][y].d = 1;
        map[x][y].l = 0;
        map[x][y].r = 0;
    }
    else if(s[x][y]=='F')
    {
        map[x][y].u = 0;
        map[x][y].d = 0;
        map[x][y].l = 1;
        map[x][y].r = 1;
    }
    else if(s[x][y]=='G')
    {
        map[x][y].u = 1;
        map[x][y].d = 0;
        map[x][y].l = 1;
        map[x][y].r = 1;
    }
    else if(s[x][y]=='H')
    {
        map[x][y].u = 1;
        map[x][y].d = 1;
        map[x][y].l = 1;
        map[x][y].r = 0;
    }
    else if(s[x][y]=='I')
    {
        map[x][y].u = 0;
        map[x][y].d = 1;
        map[x][y].l = 1;
        map[x][y].r = 1;
    }
    else if(s[x][y]=='J')
    {
        map[x][y].u = 1;
        map[x][y].d = 1;
        map[x][y].l = 0;
        map[x][y].r = 1;
    }
    else if(s[x][y]=='K')
    {
        map[x][y].u = 1;
        map[x][y].d = 1;
        map[x][y].l = 1;
        map[x][y].r = 1;
    }
}
int insert(int nx,int ny,int x,int y,int d)
{
    if(d==0)
    {
        if(map[x][y].r&&map[nx][ny].l)
            return 1;
    }
    else if(d==1)
    {
        if(map[x][y].l&&map[nx][ny].r)
            return 1;
    }
    else if(d==2)
    {
        if(map[x][y].d&&map[nx][ny].u)
            return 1;
    }
    else if(d==3)
    {
        if(map[x][y].u&&map[nx][ny].d)
            return 1;
    }
    return 0;
}
int find(int x)
{
    return x==p[x]?x:p[x]=find(p[x]);
}
int Union(int x,int y)
{
    int nx = find(x);
    int ny = find(y);
    if(nx!=ny)
        p[ny] = nx;
}
int dfs(int x,int y)
{
    for(int i = 0; i < 4; i++)
    {
        int nx = dx[i]+x;
        int ny = dy[i]+y;
        if(nx>=0&&nx<n&&ny>=0&&ny<m)
            if(!vis[nx][ny]&&insert(nx,ny,x,y,i))
            {
                vis[nx][ny] = 1;
                Union(x*m+y,nx*m+ny);
                dfs(nx,ny);
            }
    }
}
int solve()
{
    int ans=0;
    memset(vis,0,sizeof(vis));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(!vis[i][j])
            {
                vis[i][j] = 1;
                ans++;
                dfs(i,j);
            }

    /*for(int i = 0; i < n*m; i++)
        if(p[i]==i)
            ans++;*/
    printf("%d\n",ans);
}
int main()
{
    while(scanf("%d %d",&n,&m)==2)
    {
        if(n<0||m<0) break;
        memset(map,0,sizeof(map));
        for(int i = 0; i < n*m; i++)
            p[i] = i;
        for(int i = 0; i < n; i++)
        {
            scanf("%s",s[i]);
            for(int j = 0; j < m; j++)
                build(i,j);
        }
        solve();
    }
    return 0;
}