给一个n×n的01矩阵，你的任务是将尽量少的0变成1，是的每个元素的上下左右的位置（如果存在的话）的之和均为偶数。1<=n<=15.
如果暴力整个矩阵，那么时间复杂度是O（2^(n*n)） 。
其实，我们只需要暴力第一行就行了， 只要第一行确定了， 那么为了让第一行满足性质，那么第二行的元素的值也随之确定，那么第三，第。。。。也是。
那么时间复杂度是O（(2^n ) * n*n）.
挺多的开关问题有这样的性质，只要第一行或者第一个确定了， 那么随后的也就确定了。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N = 20; const int INF = 1<<30; int dx[] = {0,0,-1}; int dy[] = {-1,1,0}; int a[N][N]; int tmp[N][N]; int ans; int getSum(int x, int y, int n) { int ret = 0; for(int i=0;i<3;++i) { int tx = x + dx[i]; int ty = y + dy[i]; if(tx>=1 && tx<=n && ty>=1 && ty<=n) ret += tmp[tx][ty]; } return ret; } int check(int s, int n) { for(int i=1;i<=n;++i) { tmp[1][i] = s&1; if(tmp[1][i]==0 && a[1][i]==1) return INF; s>>=1; } for(int i=2;i<=n;++i) { for(int j=1;j<=n;++j) { int ret = getSum(i-1,j,n); tmp[i][j] = ret & 1; if(tmp[i][j]==0 && a[i][j]==1) return INF; } } int cnt = 0; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) cnt += a[i][j] != tmp[i][j]; return cnt; } int main() { int t,n; scanf("%d",&t); for(int cas=1;cas<=t;++cas) { scanf("%d",&n); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%d",&a[i][j]); ans = INF; for(int s=0;s<=(1<<n)-1;++s) { ans = min(ans,check(s,n)); } if(ans==INF) printf("Case %d: %d ",cas, -1); else printf("Case %d: %d ",cas ,ans); } return 0; }