本文主要是介绍UVa 11464 Even Parity / 深搜，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
算是一类的题目 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");elseprintf("%d\n",min);}return 0;
}
这篇关于UVa 11464 Even Parity / 深搜的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
