UVA 11464 Even Parity

1645 ワード

n*nの0、1行列(要素は0か1か)を与え、できるだけ少ない0を1に変更し、(1は0に変更できない)各要素の上下左右の要素(存在する場合)の和が偶数になるようにする.
すべてを列挙すると、効率が非常に低くなります.
最初の行を列挙するだけでは、数は相対的に小さくなります.
第1行から第2行を推定し,第2行は第3行を推定し,最後に元の行列と比較した.できます.
c++STLのnext_を使いましたpermutationは次の配列を求めます^
しかし、判断途中で条件に合わずgotoで飞び出して提出するとCompilation errorに报告します..
T T Tはいつ次のG++に行かなければなりませんか.VSでも過ごせるわ.
#include<iostream> 
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std; 
const int MAXN=20;
const int INF=100000;
int a[MAXN][MAXN],b[MAXN][MAXN],n,ans;
void check(int num)
{
	memset(b,0,sizeof(b));
	if(num)
	for(int i=n-1;i>=num-1;i--)
		b[0][i]=1;
	do
	{
		bool ok=true;
		for(int i=0;i<n-1;i++)
		{			
			for(int j=0;j<n;j++)
			{
				int sum=0;
				if(i>0) sum+=b[i-1][j];//up
				if(j>0) sum+=b[i][j-1];//left
				if(j<n-1) sum+=b[i][j+1];//right
				b[i+1][j]=sum%2;
				if(a[i+1][j]==1&&b[i+1][j]==0) 
				{ok=false;break;}		//  goto      。。
			}
			if(!ok) break;
		}
		int count=0;
	
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				if(a[i][j]!=b[i][j])
				{
					if(a[i][j]==1&&b[i][j]==0) 
					{ok=false;break;}
					count++;
				}
			}
			if(!ok)break;
		}
		if(ok)
			ans=min(ans,count);			
	}
	while(next_permutation(b[0],b[0]+n));

}
int main()  
{
	int repeat,ri;
	scanf("%d",&repeat);
	for(ri=1;ri<=repeat;ri++)
	{		
		ans=INF;
		scanf("%d",&n);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				cin>>a[i][j];
		for(int i=0;i<=n;i++)
			check(i);
		printf("Case %d: %d
",ri,ans!=INF?ans:-1); } }