算是一类的题目 zoj也看到过 今天终于写了
给你一个0 1 的矩阵 可以把0变成1 1 不能变成0 然后最小的变换次数是每一个位置的上下左右加起来的和是偶数
枚举第一行 根据第一行下面的都已经确定了 O(2^n*N*N)
#include <stdio.h> #include <string.h> const int MAX = 20; int n; int min; int a[MAX][MAX]; int b[MAX][MAX]; int check() { int i,j,sum,cnt = 0; for(i = 0;i < n; i++) { if(a[0][i] == 1 && b[0][i] == 0) { return 0x7ffffff; } else if(a[0][i] != b[0][i]) cnt++; } for(i = 1; i < n; i++) { for(j = 0; j < n; j++) { sum = 0; if(i > 1) sum += b[i-2][j]; if(j > 0) sum += b[i-1][j-1]; if(j < n - 1) sum += b[i-1][j+1]; b[i][j] = sum % 2; if(a[i][j] == 1 && b[i][j] == 0) return 0x7ffffff; else if(a[i][j] != b[i][j]) cnt++; } } return cnt; } void dfs(int k) { if(k == n) { int res = check(); if(min > res) min = res; return; } b[0][k] = 0; dfs(k+1); b[0][k] = 1; dfs(k+1); } int main() { int t,i,j,cas = 1; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i = 0; i < n; i++) for(j = 0; j < n; j++) scanf("%d",&a[i][j]); min = 0x7ffffff; dfs(0); printf("Case %d: ",cas++); if(min == 0x7ffffff) puts("-1"); else printf("%d\n",min); } return 0; }
