uva11464（递推关系）

/* translation: 给出一个矩阵，每个数字要么0要么是1。可以将若干个0变换成1,问最少需要多少个这样的变换才能使得矩阵变成 偶数矩阵。一个偶数矩阵里面每一个数字的上下左右数字加起来的和都是偶数。 solution: 递推 关键是找到递推关系。因为一行最多只要15个数字，所以可以暴力枚举出第一行的状态。然后根据第一行的状态其实就可以确定下一行 的状态了。进而就可以推出整个矩阵的状态了。不断更新迭代，即可找到答案。 */ #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 15; const int INF = 0x3f3f3f3f; int grid[maxn + 5][maxn + 5], n; bool check(int s, int row) { for(int col = 0; col < n; col++) { if(grid[row][col] == 1 && !(s >> (n - 1 - col) & 1)) return false; } return true; } int count_bit(int s, int row) { int res = 0; for(int col = 0; col < n; col++) { if(grid[row][col] == 0 && s >> (n - 1 - col) & 1) res++; } return res; } int get_bit(int s, int p) { if(p < 0 || p >= n) return 0; if(s >> p & 1) return 1; else return 0; } int generate_next(int last_s, int s) { int next_s = 0; for(int i = 0; i < n; i++) { if((get_bit(s, i+1) + get_bit(s, i-1) + get_bit(last_s, i)) & 1) { next_s |= 1 << i; } } return next_s; } int calculate(int s, int last_s) { int res = 0; for(int i = 0; i < n; i++) { if(!check(s, i)) return INF; res += count_bit(s, i); int next_s = generate_next(last_s, s); last_s = s; s = next_s; } return res; } int main() { //freopen("in.txt", "r", stdin); int T, kase = 0; scanf("%d", &T); while(T--) { scanf("%d", &n); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { scanf("%d", &grid[i][j]); } } int status = 0; for(int i = 0; i < n; i++) if(grid[0][n-i-1]) status |= 1 << i; int res = INF; for(int s = status; s < 1 << n; s++) { res = min(res, calculate(s, 0)); //printf("# = %d\n", calculate(s, 0)); } if(res >= INF) res = -1; printf("Case %d: %d\n", ++kase, res); } return 0; }