首页 > 代码库 > UVa 11464 偶数矩阵

UVa 11464 偶数矩阵

2024-09-07 05:41:56   214人阅读

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 偶数矩阵


联系
我们