首页 > 代码库 > UVa11464 Even Parity (枚举子集)

UVa11464 Even Parity (枚举子集)

2024-08-12 06:02:34   217人阅读

链接：http://acm.hust.edu.cn/vjudge/problem/24665
分析：枚举第0行的情况，接下来可以根据第0行计算出第1行，根据第1行计算出第2行...方法是当确定B[r][c]是0还是1时（前提要合法），根据B[r-1][c]的上，左，右3个元素之和来判断，如果出现将原来是1的变为0则不合法返回INF，最后统计下原来是0后来变为1的个数cnt,然后返回更新ans被改变元素的最小个数即可。

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5  6 const int INF = 1e9; 7 const int maxn = 15 + 5; 8  9 int n, A[maxn][maxn], B[maxn][maxn];10 11 int check(int s) {12     for (int c = 0; c < n; c++)13         if (s & (1 << c)) B[0][c] = 1;14         else if (A[0][c]) return INF;15         else B[0][c] = 0;16     for (int r = 1; r < n; r++)17         for (int c = 0; c < n; c++) {18             int sum = 0;19             if (r > 1) sum += B[r - 2][c];20             if (c > 0) sum += B[r - 1][c - 1];21             if (c < n - 1) sum += B[r - 1][c + 1];22             B[r][c] = sum % 2;23             if (A[r][c] == 1 && B[r][c] == 0) return INF;24         }25     int cnt = 0;26     for (int r = 0; r < n; r++)27         for (int c = 0; c < n; c++)28             if (A[r][c] != B[r][c]) cnt++;29     return cnt;30 }31 32 int main() {33     int T;34     scanf("%d", &T);35     for (int kase = 1; kase <= T; kase++) {36         scanf("%d", &n);37         for (int r = 0; r < n; r++)38             for (int c = 0; c < n; c++)39                 scanf("%d", &A[r][c]);40         int ans = INF;41         for (int s = 0; s < (1 << n); s++)42             ans = min(ans, check(s));43         if (ans == INF) ans = -1;44         printf("Case %d: %d\n", kase, ans);45     }46     return 0;47 }

 

UVa11464 Even Parity (枚举子集)


联系
我们