首页 > 代码库 > UVa 11464 偶数矩阵
UVa 11464 偶数矩阵
https://vjudge.net/problem/UVA-11464
题意：
给出一个01矩阵，把尽量少的0变成1，使得每个元素的上下左右的元素之和均为偶数。
思路：
用二进制枚举第一行的情况，之后每一行都可以由上一行推导得出。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<string> 5 using namespace std; 6 7 #define INF 10000000 8 int g[20][20]; 9 int G[20][20];10 int N;11 12 int check(int s) 13 {14 memset(G, 0, sizeof(G));15 for (int i = 0; i < N; i++){16 if (s & (1 << i)) G[0][i] = 1;17 else if (g[0][i] == 1) return INF;18 }19 for (int i = 1; i < N; i++) 20 {21 for (int j = 0; j < N; j++)22 {23 int sum = 0;24 if (i > 1) sum += G[i - 2][j];25 if (j > 0) sum += G[i - 1][j - 1];26 if (j < N - 1) sum += G[i - 1][j + 1];27 G[i][j] = sum % 2;28 if (g[i][j] == 1 && G[i][j] == 0) return INF;29 }30 }31 int cnt = 0;32 for (int i = 0; i <N; i++)33 for (int j = 0; j < N; j++) {34 if (G[i][j] != g[i][j])35 cnt++;36 }37 return cnt;38 }39 int main() 40 {41 //freopen("D:\\txt.txt", "r", stdin);42 int T;43 cin >> T;44 for (int kase = 1; kase <= T;kase++)45 {46 scanf("%d", &N);47 for (int i = 0; i < N; i++)48 for (int j = 0; j < N; j++)49 scanf("%d", &g[i][j]);50 int ans = INF;51 52 for (int i = 0; i < (1 << N); i++) {53 ans = min(ans, check(i));54 }55 printf("Case %d: ", kase);56 if (ans == INF) printf("-1\n");57 else printf("%d\n", ans);58 }59 return 0;60 }
UVa 11464 偶数矩阵
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。