首页 > 代码库 > UVa11464 Even Parity (枚举子集)
UVa11464 Even Parity (枚举子集)
链接: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 (枚举子集)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。