UVa 11464 Even Parity

当前位置 : 首页 > 网页制作 > CSS > UVa 11464 Even Parity

UVa 11464 Even Parity

来源: 作者: 时间:2016-01-28 09:27
算是一类的题目 zoj也看到过 今天终于写了给你一个0 1 的矩阵 可以把0变成1 1 不能变成0 然后最小的变换次数是每一个位置的上下左右加起来的和是偶数枚举第一行 根据第一行下面的都

算是一类的题目 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"); else printf("%d\n",min); } return 0; }

 

Tag:
网友评论

<