1 条题解
-
0
C++ :
#include <iostream> #include <cstring> #include <cstdio> #define Maxn 203 using namespace std; int G[Maxn][Maxn]={0}; int n,m,color=0; int father[2*Maxn*Maxn]={0}; int tot[Maxn*Maxn]={0}; int ind[Maxn*Maxn]={0},outd[Maxn*Maxn]={0}; bool flag[Maxn*Maxn]={0}; char a[Maxn][Maxn],b[Maxn][Maxn]; int find(int x) { if(father[x]!=x) father[x]=find(father[x]); return father[x]; } void unionn(int x,int y) { int r1=find(x); int r2=find(y); if(r1!=r2) father[r2]=r1; } int abs(int x) { if(x>0) return x; return -x; } void build() { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(a[i][j]=='X'||a[i][j]=='/') { if(!G[i][j-1]) { G[i][j-1]=++color; father[color]=color; } if(!G[i-1][j]) { G[i-1][j]=++color; father[color]=color; } outd[G[i][j-1]]++; outd[G[i-1][j]]++; unionn(G[i][j-1],G[i-1][j]); } if(a[i][j]=='X'||a[i][j]=='\\') { if(!G[i][j]) { G[i][j]=++color; father[color]=color; } if(!G[i-1][j-1]) { G[i-1][j-1]=++color; father[color]=color; } outd[G[i][j]]++; outd[G[i-1][j-1]]++; unionn(G[i][j],G[i-1][j-1]); } } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(b[i][j]=='X'||b[i][j]=='/') { if(!G[i][j-1]) { G[i][j-1]=++color; father[color]=color; } if(!G[i-1][j]) { G[i-1][j]=++color; father[color]=color; } ind[G[i][j-1]]++; ind[G[i-1][j]]++; unionn(G[i][j-1],G[i-1][j]); } if(b[i][j]=='X'||b[i][j]=='\\') { if(!G[i][j]) { G[i][j]=++color; father[color]=color; } if(!G[i-1][j-1]) { G[i-1][j-1]=++color; father[color]=color; } ind[G[i][j]]++; ind[G[i-1][j-1]]++; unionn(G[i][j],G[i-1][j-1]); } } } for(int i=1;i<=color;i++) { if(ind[i]||outd[i]) { int t=find(i); if(!flag[t]) flag[t]=true; tot[t]+=abs(ind[i]-outd[i]); } } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>b[i][j]; } } build(); int ans=0; for(int i=1;i<=color;i++) { if(find(i)==i) { if(tot[i]!=0) ans+=abs(tot[i])/2; else ans++; } } cout<<ans<<endl; return 0; }
- 1
信息
- ID
- 1848
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者