- 十字绣
- 2017-03-14 17:17:36 @
#include<iostream>
#include<cstdlib>
#include<cstdio>
int n,m;
char map[2][205][205];
int a[50000],v[50000];
int c[50000],b[50000],u[50000];
int father[50000];
int ans=0;
int find(int x)
{
if(father[x]==x) return x;
else return find(father[x]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=(m+1)*(n+1)-1;i++)
{
father[i]=i;
}
for(int k=0;k<2;k++)
for(int i=0;i<n;i++)
scanf("%s",map[k][i]);
for(int k=0;k<2;k++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(map[k][i][j]=='\\' || map[k][i][j]=='X')
{
int f1=find((m+1)*i+j);
int f2=find((m+1)*(i+1)+j+1);
if(f1!=f2) father[f2]=f1;
a[(m+1)*i+j]+=(-2)*k+1;
a[(m+1)*(i+1)+j+1]+=(-2)*k+1;
v[(m+1)*i+j]=v[(m+1)*(i+1)+j+1]=1;
}
if(map[k][i][j]=='/' || map[k][i][j]=='X')
{
int f1=find((m+1)*i+j+1);
int f2=find((m+1)*(i+1)+j);
if(f1!=f2) father[f2]=f1;
a[(m+1)*i+j+1]+=(-2)*k+1;
a[(m+1)*(i+1)+j]+=(-2)*k+1;
v[(m+1)*i+j+1]=v[(m+1)*(i+1)+j]=1;
}
}
}
}
for(int i=0;i<(n+1)*(m+1);i++)
{
if(v[i]==0) continue;
int j=find(i);
if(u[j]==0) {u[j]=1;c[++c[0]]=j;}
b[j]+=abs(a[i]);
}
for(int i=1;i<=c[0];i++)
{
if(b[c[i]]==0)ans++;
else ans+=b[c[i]]/2;
}
printf("%d\n",ans);
return 0;
}
1 条评论
-
doc LV 10 MOD @ 2017-03-15 01:13:29
已重测
- 1