题意：给你一个nxn的矩阵01矩阵，（每个元素非0就1），你的任务是把尽量少的0变成1，使矩阵的每个元素的上下左右的元素只和均为偶数。
方法：枚举每个数字变或者不变有2^255太大。但是枚举第一行只有2^15，然后根据第一行计算下边的就行。注意是从上到下，从左到右计算，也就是得到的肯定是满足题意的。如果出现矛盾，则这种枚举不合适，返回INF。
#include#include #include #include #include #include #include #include #include #include using namespace std; const int maxn = 20; const int INF = 100000000; int n, A[maxn][maxn], B[maxn][maxn]; int check(int s) { int c = 0, r = 0; memset(B, 0, sizeof(B)); for (c = 0; c < n; c++) { if (s & (1 << c)) B[0][c] = 1; else if (A[0][c] == 1) return INF; } for (r = 1; r < n; r++) { for (c = 0; c < n; c++) { int sum = 0; if (r > 1) sum += B[r-2][c]; if (c > 0) sum += B[r-1][c-1]; if (c < n-1) sum += B[r-1][c+1]; B[r][c] = sum % 2; if (A[r][c] == 1 && B[r][c] == 0) return INF; } } int cnt = 0; for (r = 0; r < n; r++) for (c = 0; c < n; c++) if (A[r][c] != B[r][c]) cnt++; return cnt; } int main() { #ifdef Local freopen("a.in", "r", stdin); #endif int t = 0, i = 0, j = 0, c = 0, r = 0; cin >> t; for (i = 1; i <= t; i++) { cin >> n; for (r = 0; r < n; r++) for (c = 0; c < n; c++) cin >> A[r][c]; int ans = INF; for (j = 0; j < (1 << n); j++) ans = min(ans, check(j)); if (ans == INF) ans = -1; cout << "Case "<< i << ": " << ans << endl; } }
1、不知道是vs还是格式的问题，括号该打上就打上，别看着格式对就不打了，调试的时候因为check中一个循环没打，造成下一个循环c不变，一直是3。
2、注意理解
if (A[r][c] == 1 && B[r][c] == 0) return INF;