首页 > 代码库 > HDU 5652 India and China Origins(经典并查集)

HDU 5652 India and China Origins(经典并查集)

特别经典的一个题,还有一种方法就是二分+bfs

题意:空间内n*m个点,每个点是0或者1,0代表此点可以走,1代表不能走。接着经过q年,每年一个坐标表示此点不能走。问哪年开始图上不能出现最上边不能到达最下边的情况了

 

图上连通性可以使用并查集判断,但是并查集不善于删边,却善于添边。所以我们倒着来想就是离线倒序添边(横向并查,再纵向并查),当某次判断时图已经连通,就结束。

我使用二维并查集,其实就是使用结构体代替一维数组。接着就是每次一定要从x轴小的点到达x轴大的点,最后注意添边时,我们需要此点向四个方向判断添边

 

#include<set>#include<map>#include<queue>#include<stack>#include<cmath>#include<vector>#include<string>#include<cstdio>#include<cstring>#include<stdlib.h>#include<iostream>#include<algorithm>using namespace std;#define eps 1E-8/*注意可能会有输出-0.000*/#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0#define mul(a,b) (a<<b)#define dir(a,b) (a>>b)typedef long long ll;typedef unsigned long long ull;const int Inf=1<<28;const double Pi=acos(-1.0);const int Mod=1e9+7;const int Max=510;struct node{    int xx,yy;} fat[Max][Max]; //二维并查集int xx1[Max*Max],yy1[Max*Max];char str[Max][Max];int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}}; //四个方向void Init(int n,int m){    for(int i=0; i<n; ++i)    {        for(int j=0; j<m; ++j)        {            fat[i][j].xx=i;            fat[i][j].yy=j;        }    }    return ;}node Find(int x,int y){    if(x==fat[x][y].xx&&y==fat[x][y].yy)        return fat[x][y];    return fat[x][y]=Find(fat[x][y].xx,fat[x][y].yy);}int Union(int xx1,int yy1,int xx2,int yy2)//合并两个二维并查集{    //printf("%d %d %d %d\n",xx1,yy1,xx2,yy2);    node xy1=Find(xx1,yy1);    node xy2=Find(xx2,yy2);    if(xy1.xx==xy2.xx&&xy1.yy==xy2.yy)        return 0;    if(xy1.xx<xy2.xx)//保证向下就好        fat[xy1.xx][xy1.yy]=xy2;    else        fat[xy2.xx][xy2.yy]=xy1;    return 1;}int Jud(int n,int m)//判断是否连通{    for(int i=0; i<m; ++i)    {        node xy1=Find(0,i);//第一行可以到达的最下方位置        if(xy1.xx==n-1)            return 1;    }    return 0;}int Solve(int n,int m,int q){    for(int i=0; i<n; ++i)    {        for(int j=0; j<m-1; ++j)        {            if(str[i][j]==0&&str[i][j+1]==0)            {                int ans=Union(i,j,i,j+1);//横向合并                //printf("%d\n",ans);            }        }    }    for(int j=0; j<m; ++j)    {        for(int i=0; i<n-1; ++i)        {            if(str[i][j]==0&&str[i+1][j]==0)            {                int ans=Union(i,j,i+1,j);//纵向合并                //printf("ver=%d\n",ans);            }        }    }    if(Jud(n,m))        return -1;    int p;    for(int i=q-1; i>=0; --i)    {        p=0;        str[xx1[i]][yy1[i]]=0;        while(p<4)        {            if(xx1[i]+dir[p][0]>=0&&xx1[i]+dir[p][0]<n&&yy1[i]+dir[p][1]>=0&&yy1[i]+dir[p][1]<m&&str[xx1[i]+dir[p][0]][yy1[i]+dir[p][1]]==0)//需要连接四个方向可行的地方             Union(xx1[i],yy1[i],xx1[i]+dir[p][0],yy1[i]+dir[p][1]);            p++;        }        if(Jud(n,m))            return i+1;    }        return 0;}int main(){    int t,n,m,q;    scanf("%d",&t);    while(t--)    {        scanf("%d %d",&n,&m);        Init(n,m);        for(int i=0; i<n; ++i)            scanf("%s",str[i]);        scanf("%d",&q);        for(int i=0; i<q; ++i) //存下来,倒着增加边        {            scanf("%d %d",&xx1[i],&yy1[i]);            str[xx1[i]][yy1[i]]=1;        }        printf("%d\n",Solve(n,m,q));    }    return 0;}

 

HDU 5652 India and China Origins(经典并查集)