首页 > 代码库 > 【UVA】11464-Even Parity(二进制枚举子集)
【UVA】11464-Even Parity(二进制枚举子集)
枚举第一行的所有可能情况,之后根据上面行计算下面行(判断是否冲突),获得最终结果。
14058243 | 11464 | Even Parity | Accepted | C++ | 0.275 | 2014-08-18 05:14:15 |
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<list> #include<cmath> #include<string> #include<sstream> #include<ctime> using namespace std; #define _PI acos(-1.0) #define esp 1e-9 #define INF 1 << 30 typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pill; /*=========================================== ===============KinderRiven=================== ===========================================*/ #define MAXD 15 + 5 int n; int Map[MAXD][MAXD]; int solve(int u){ int MAP[MAXD][MAXD]; int ans = 0; memcpy(MAP,Map,sizeof(MAP)); for(int i = 0 ; i < n ; i++){ if(!((u >> i) & 1)) continue; else{ if(MAP[0][i] == 1); else{ MAP[0][i] = 1; ans ++; } } } for(int i = 1 ; i < n ; i ++) for(int j = 0 ; j < n ; j ++){ int sum = 0; if(i > 1) sum += MAP[i - 2][j]; if(j > 0) sum += MAP[i - 1][j - 1]; if(j < n - 1) sum += MAP[i - 1][j + 1]; int t = sum % 2; /*已经是偶数了*/ if(t == 0){ if(MAP[i][j] == 1) return INF; } else{ if(MAP[i][j] == 0){ MAP[i][j] = 1; ans ++; } } } return ans; } int main(){ int T; scanf("%d",&T); for(int Case = 1;Case <= T; Case ++){ int ans = INF; scanf("%d",&n); for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < n ; j++) scanf("%d",&Map[i][j]); for(int i = 0 ; i < (1 << n) ; i++) ans = min(ans,solve(i)); printf("Case %d: ",Case); if(ans >= INF) printf("-1\n"); else printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。