UVA 11464 Even Parity (独特思路) - c++编程基础

题意：有一个n*n的01矩阵，任务是把尽可能少的0变成1，使得每个元素的上、下、左、右元素之和为偶数。
思路：很容易想到的思路是枚举每个点是0还是1，因为n<=15，复杂度就是2^225显然TLE。注意到每次确定一样以后，下一行就是可以被确定的！所以，只要枚举第一行的状态，就可以推出每一行的状态，复杂度是15*2^15

#include
#include
#define INF 0x3f3f3f3f
#define MAXN 20
using namespace std;

int n,ori[MAXN][MAXN],t[MAXN][MAXN],dx[]={0,0,-1},dy[]={1,-1,0},ans,ca=0,T;

bool f(int x,int y)
{
    int sum=0;
    for(int i=0;i<3;++i) 
        if(x+dx[i]>=0 && y+dy[i]>=0 && x+dx[i]0
{
    for(int i=0;i




=n) {ans=min(ans,solve(step));return;}
    if(ori[0][pos]) {t[0][pos]=1;dfs(pos+1,step);}
    else 
    {
        t[0][pos]=0; dfs(pos+1,step);
        t[0][pos]=1; dfs(pos+1,step+1);
    }
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=0;i=INF  -1:ans);
    }
    return 0;
}