偶数矩阵，神答案，求解释
给定矩阵由0,1组成，使用最少的改变（使0变成1），使得任何元素的上下左右元素（如果存在）和为偶数
输入： 测试组数， 矩阵大小n ，矩阵每一个数
输出： 最小翻转次数，无法实现则输出-1
有谁能给我解释一下下面代码的check()函数和整段代码的思路，谢谢！
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))
#define MAX 10000000
struct{
int x,y;
}a[20][20];
int n;
int check(int k)
{
int i;
for(i=0;i<n;i++)
a[0][i].y=0;
i=0;
while(k)
{
a[0][i].y=k%2;
k=k/2;
i++;
}
for(i=0;i<n;i++)
if(a[0][i].x==1&&a[0][i].y==0)
return -1;
return 0;
}
int fun()
{
int i,j;
for(i=1;i<n;i++)
{
for(j=0;j<n;j++)
{
int sum=0;
if(i>=2)
sum+=a[i-2][j].y;
if(j>0)
sum+=a[i-1][j-1].y;
if(j<n-1)
sum+=a[i-1][j+1].y;
if(sum%2==0)
a[i][j].y=0;
else
a[i][j].y=1;
if(a[i][j].y==0&&a[i][j].x==1)
return MAX;
}
}
int cnt=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(a[i][j].x==0&&a[i][j].y==1)
cnt++;
return cnt;
}
int main()
{
int T;
int cas=1;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j].x);
}
}
int ans=MAX;
for(i=0;i<(1<<n);i++)
{
if(check(i)==-1)
continue;
ans=min(ans,fun());
}
if(ans!=MAX)
printf("Case %d: %d\n",cas++,ans);
else
printf("Case %d: -1\n",cas++);
}
return 0;
}
forjune
11 years ago