这是一道白书17页的题目。
题目大意：输入一个n*n的01矩阵（1<n<=15）
要求：将0置1，使每个项的前后左右之和为偶数，求最小翻动数。
暴力求解肯定不行，2^225≈5.8e76（tle）
所以想到局部枚举，下面的各行都可以依据上一行推导出。
下面给出推导下一行的例子：（3*3）
假设枚举第一行是这样，开始全为零（在下面代码中用二进制即(010)2=(2)10表示
1 0 1
0 0 0
0 0 0
从[0][0]开始：自己是1，右边是0，所以下面置1
1 0 1
1 0 0
0 0 0
[0][1]:自己是0，左边是1，右边是1，所以下面置0
1 0 1
1 0 0
0 0 0
[0][2]:自己是1，左边是0，所以下面是1
1 0 1
1 0 1
0 0 0
以此类推：
1 0 1
1 0 1
0 0 0
最后将得到的矩阵与输入的矩阵对比，不相同的为filp了的，计数
下面贴出ac代码
//#define DEBUG
#include<iostream>
#include<cstring>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long
#define maxn 16
#define INF maxn*maxn+10
using namespace std;
int a[maxn][maxn], b[maxn][maxn];
int line;
int solve(int s) {
memset(b, 0, sizeof(b));//第一行
for (int c = 0; c < line; c++)
if (s & (1 << c))//取flip位置
b[0][c] = 1;
else
if (a[0][c] == 1)
return INF;
for(int r=1;r<line;r++)
rep(c, line) {//b[r-1][c]
int sum = 0;
if (r > 1) sum += b[r - 2][c];
if (c > 0) sum += b[r - 1][c - 1];
if (c < line - 1) sum += b[r - 1][c + 1];
b[r][c] = sum % 2;
if (a[r][c] == 1 && b[r][c] == 0)
return INF;//不能将1 flip为0
}
int cnt = 0;
rep(i, line) rep(j, line)if (a[i][j] != b[i][j]) cnt++;//计算变化了多少个
return cnt;
}
int main() {
ios::sync_with_stdio(false);
int count;
cin >> count;
rep(i, count) {
cin >> line;
rep(j, line) {
rep(k, line) {
cin>>a[j][k];
}
}
int sum = INF;
for (int i = 0; i < (1<< line); i++) {//第0行暴力flip,参数：第0行为1的位置
sum = min(sum,solve(i));
}
if (sum == INF)
sum = -1;
cout << "Case " << i + 1 << ": " <<sum<< '\n';
}
#ifdef DEBUG
system("pause");
#endif //
return 0;
}
那个二进制想法挺牛的。最后要注意Case n: 后面的空格，我才不会说因为这个我这个蒟蒻pe了一次。。。
