UVA 11464 Even Parity (獨特思路)

題意：有一個n*n的01矩陣，任務是把盡可能少的0變成1，使得每個元素的上、下、左、右元素之和為偶數。
思路：很容易想到的思路是枚舉每個點是0還是1，因為n<=15，復雜度就是2^225顯然TLE。注意到每次確定一樣以後，下一行就是可以被確定的！所以，只要枚舉第一行的狀態，就可以推出每一行的狀態，復雜度是15*2^15

#include<cstdio>
#include<iostream>
#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)
{
&nbsp;&nbsp; &nbsp;int sum=0;
&nbsp;&nbsp; &nbsp;for(int i=0;i<3;++i) 
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(x+dx[i]>=0 && y+dy[i]>=0 && x+dx[i]<n && y+dy[i]<n) sum+=t[x+dx[i]][y+dy[i]];
&nbsp;&nbsp; &nbsp;return sum&1;
}

bool generate(int x,int &sum)//x>0
{
&nbsp;&nbsp; &nbsp;for(int i=0;i<n;++i)
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(f(x-1,i)) 
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;{
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;t[x][i]=1;
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(!ori[x][i]) ++sum;
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;else
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;{
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(ori[x][i]) {sum=INF;return 0;}
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;t[x][i]=0;
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}
&nbsp;&nbsp; &nbsp;return 1;
}

int solve(int pre)
{
&nbsp;&nbsp; &nbsp;int sum=pre;
&nbsp;&nbsp; &nbsp;for(int i=1;i<n;++i) if(!generate(i,sum)) break;
&nbsp;&nbsp; &nbsp;return sum;
}

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

int main()
{
&nbsp;&nbsp; &nbsp;scanf("%d",&T);
&nbsp;&nbsp; &nbsp;while(T--)
&nbsp;&nbsp; &nbsp;{
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;scanf("%d",&n);
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;for(int i=0;i<n;++i)
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;for(int j=0;j<n;++j) scanf("%d",&ori[i][j]);
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;ans=INF;
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;dfs(0,0);
&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;printf("Case %d: %d\n",++ca,ans>=INF? -1:ans);
&nbsp;&nbsp; &nbsp;}
&nbsp;&nbsp; &nbsp;return 0;
}