uva - 11464 - Even Parity（部分枚举，递推）

题意：给你一个nxn的矩阵01矩阵，（每个元素非0就1），你的任务是把尽量少的0变成1，使矩阵的每个元素的上下左右的元素只和均为偶数。

方法：枚举每个数字变或者不变有2^255太大。但是枚举第一行只有2^15，然后根据第一行计算下边的就行。注意是从上到下，从左到右计算，也就是得到的肯定是满足题意的。如果出现矛盾，则这种枚举不合适，返回INF。

#include <iostream>  
#include <iomanip>  
#include <string>  
#include <cstring>  
#include <cstdio>  
#include <queue>  
#include <stack>  
#include <algorithm>  
#include <cmath>  
#include <ctime>

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;
	}
}

2、注意理解

if (A[r][c] == 1 && B[r][c] == 0) return INF;

原文：http://blog.csdn.net/u013545222/article/details/19573557