游客 注册 | 登录
中文 | En

3217 - 十字绣

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

 考古学家发现了一块布，布上做有针线活，叫做“十字绣”，即交替地在布的两面穿线。布是一个n*m的网格，线只能在网格的顶点处才能从布的一面穿到另一面。每一段线都覆盖一个单位网格的两条对角线之一，而在绣的过程中，一针中连续的两段线必须分处布的两面。给出布两面的图案，问最少需要几针才能绣出来？一针是指针不离开布的一次绣花过程。

题目输入

 第1行两个数N和M。 

<span><span>&nbsp;&nbsp;&nbsp; </span></span><span style="font-family:宋体;">接下来</span><span>N</span><span style="font-family:宋体;">行每行</span><span>M</span><span style="font-family:宋体;">个数描述正面。</span><span> </span>


<span><span>&nbsp;&nbsp;&nbsp; </span></span><span style="font-family:宋体;">再接下来</span><span>N</span><span style="font-family:宋体;">行每行</span><span>M</span><span style="font-family:宋体;">个数描述反面。</span><span></span>


<span style="font-family:宋体;">每个格子用</span><span>.</span><span style="font-family:宋体;">（表示空）</span><span>,/</span><span style="font-family:宋体;">（表示从右上角连到左下角）</span><span>,\</span><span style="font-family:宋体;">（表示从左上角连到右下角）和</span><span>X</span><span style="font-family:宋体;">（表示连两条对角线）表示。</span><span></span>

题目输出

 一个数，最少要用的针数。

输入/输出样例

输入格式

4 5
.....
.\...
..\..
.....
.....
....\
.\X..
.....

输出格式

4

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;
}
请先登陆