hdu1198 二维并查集

将A-K的上下左右有出水口的标记为1，否则标记为0。在地图中根据两个方块的位置关系，判断出水口是否相接。扫描地图时，只需要判断当前方块和上边或者左边是否相接。

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<string>
#include<map>
#include<set>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<sstream>
#define LL long long
#define OJ_DEBUG 0
#define READ_FILE 1
using namespace std;
const int NN_MAX = 510;
const int MM_MAX = 100010;
const int INF = 0x1fffffff;
/**********************************************************/
int p[NN_MAX][NN_MAX],vis[NN_MAX][NN_MAX];
int rela[][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}
};
int lx[]={-1,0},ly[]={0,-1};
char s[NN_MAX][NN_MAX];
/**********************************************************/
int min_2 (int x,int y) {return x<y?x:y;}
int max_2 (int x,int y) {return x>y?x:y;}
int find(int i,int j) {return i*100+j==p[i][j]?p[i][j]:p[i][j]=find(p[i][j]/100,p[i][j]%100);}
bool merge(int i1,int j1,int i2,int j2)
{
    int x=find(i1,j1),y=find(i2,j2);
    if(x!=y){ p[x/100][x%100]=y; return true;}
    return false;
}
bool hasRela(int x1,int y1,int x2,int y2,int v)
{
    int x=s[x1][y1]-'A',y=s[x2][y2]-'A';
    int i;
    if(v==0) i=0;
    else if(v==1) i=2;
    if(rela[x][i]&&rela[y][i^1])
        return true;
    return false;
}
/**********************************************************/
int main()
{
    if (READ_FILE) freopen ("in.txt","r",stdin);
    int m,n;
    while(scanf("%d %d",&m,&n)&&m!=-1&&n!=-1)
    {
        for(int i=0;i<m;i++)
            scanf("%s",s[i]);
        for(int i=0;i<=m;i++)
            for(int j=0;j<=n;j++)
                p[i][j]=i*100+j;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                for(int k=0;k<2;k++)
                    if( i+lx[k]>=0 && i+lx[k]<m && j+ly[k]>=0 && j+ly[k]<n && hasRela(i,j,i+lx[k],j+ly[k],k) )
                        merge(i,j,i+lx[k],j+ly[k]);
        int cnt=0;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                if(i*100+j==find(i,j))
                    cnt++;
            }
        printf("%d\n",cnt);
    }
    return 0;
}