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でも過ごせるわ.
すべてを列挙すると、効率が非常に低くなります.
最初の行を列挙するだけでは、数は相対的に小さくなります.
第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);
}
}