p15頁

給你一個n*n的01矩陣，只能夠將0變成1，使得每個元素上下左右之和均是偶數，

比如 ? 0 0 0 ? ? ? ?0 1 0

　　 ? 1 0 0>>>>1 0 1

　　 ? 0 0 0 ? ? ? ?0 1 0 ? ?一個轉變了3步

?

多實例T ?然后一個n（n<=15） ?表示n*n的矩陣 ?然后n*n個01整數 ? ?如果不能轉換 輸出-1

因為n*n的矩陣 而且n<16所以狀態壓縮 ? 遍歷最上面的一層

#include<cstdio>
#include<math.h>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
#define N 20
int a[N][N],q[N][N],n;
int Q(int s)
{memset(q,0,sizeof(q));for(int i=0;i<n;i++){if(s&(1<<i)) q[0][i]=1;///直接換為1 else if(a[0][i]==1) return INF;///如果已經是1   避免重復使用
    }for(int i=1;i<n;i++){for(int j=0;j<n;j++){///要從第0層  開始往下推int sum=0;///q[i-1][j]上左右的元素和if(i>1) sum+=q[i-2][j];if(j>0) sum+=q[i-1][j-1];if(j<n-1) sum+=q[i-1][j+1];q[i][j]=sum%2;if(a[i][j]==1&&q[i][j]==0) return INF;}///0 0 和1 1 和0，1都滿足狀態
    }int ans=0;for(int i=0;i<n;i++)///統計轉變的次數
    {for(int j=0;j<n;j++)if(a[i][j]!=q[i][j]) ans++;}return ans;
}
int main()
{int T;scanf("%d",&T);while(T--)///這道題的整體思想  是改變最上面一層的數 然后根據規律向下遞推
    {scanf("%d",&n);for(int i=0;i<n;i++){for(int j=0;j<n;j++)scanf("%d",&a[i][j]);}int ans=INF;for(int i=0;i<(1<<n);i++)///利用狀態壓縮 將最上面的每種情況 都考慮到ans=min(ans,Q(i));if(ans==INF) ans=-1;///如果不能轉換則輸出-1printf("%d\n",ans);}return 0;
}