首页 > 代码库 > hdu5652:India and China Origins(并查集)
hdu5652:India and China Origins(并查集)
倒序操作用并查集判断是否连通,新技能get√(其实以前就会了
这题细节很多。。。搞得整个程序都是调试输出,几度看不下去想要重写
并查集到现在大概掌握了两个基本用途:判断是否连通 / 路径压缩(上一篇blog)
#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #define ll long long using namespace std; const int dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1},maxn=500010; int n,m,china,india,T,q,fa[maxn],x[maxn],y[maxn]; bool v[510][510],map[510][510],map2[510][510]; char s[maxn]; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar(); while(c<=‘9‘&&c>=‘0‘)k=k*10+c-‘0‘,c=getchar(); k*=f; } int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);} int bh(int x,int y) { if(x==0)return n*m+1; if(x==n+1)return n*m+2; return (x-1)*m+y; } void dfs(int x,int y) { v[x][y]=1; for(int i=1;i<=4;i++) { int nx=x+dx[i],ny=y+dy[i]; if(nx>n||nx<1||ny>m||ny<1)continue; if((!v[nx][ny])&&(!map[nx][ny])&&(!map2[nx][ny])) fa[gf(bh(nx,ny))]=gf(bh(x,y)),dfs(nx,ny); } } int main() { read(T); while(T--) { memset(v,0,sizeof(v)); memset(map,0,sizeof(map)); memset(map2,0,sizeof(map2)); read(n);read(m);china=n*m+1;india=n*m+2; for(int i=1;i<=n;i++) { scanf("%s",s); for(int j=0;j<m;j++) map[i][j+1]=s[j]-‘0‘; } read(q); for(int i=1;i<=q;i++) { read(x[i]);read(y[i]); x[i]++;y[i]++; map2[x[i]][y[i]]=1; } for(int i=1;i<=n*m+2;i++)fa[i]=i; for(int i=1;i<=m;i++) if((!map[1][i])&&(!v[1][i])&&(!map2[1][i]))fa[gf(bh(1,i))]=gf(china),dfs(1,i); for(int i=1;i<=m;i++) if((!map[n][i])&&(!v[n][i])&&(!map2[n][i]))fa[gf(bh(n,i))]=gf(india),dfs(n,i); for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) if((!map[i][j])&&(!v[i][j])&&(!map2[i][j]))dfs(i,j); if(gf(china)==gf(india))printf("-1\n"); else for(int i=q;i;i--) { map2[x[i]][y[i]]=0; for(int j=1;j<=4;j++) if((!map[x[i]+dx[j]][y[i]+dy[j]])&&(!map2[x[i]+dx[j]][y[i]+dy[j]])) fa[gf(bh(x[i]+dx[j],y[i]+dy[j]))]=gf(bh(x[i],y[i])); if(gf(china)==gf(india)) { printf("%d\n",i); break; } } } return 0; }
hdu5652:India and China Origins(并查集)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。