首页 > 代码库 > UVA 11464 Even Parity
UVA 11464 Even Parity
#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 20const int INF = 0x3f3f3f3f ;int sta;int res[MAXN][MAXN];int ty[MAXN][MAXN];int N;int getans(int sta,int cnt){ int ans = cnt; //printf("ans = %d\n",ans); for (int i = 1; i < N; i++) for (int j = 0 ; j < N; j++) { int sum = 0; if (i > 1) sum += ty[i - 2][j]; if (j > 0) sum += ty[i - 1][j - 1]; if (j < N - 1) sum +=ty[i - 1][j + 1]; ty[i][j] = sum % 2; if (ty[i][j] == 0 && res[i][j] == 1) return INF; } for (int i = 1; i < N; i++) for (int j = 0 ; j < N; j++) if (ty[i][j] != res[i][j]) ans++; // printf("ans =%d\n\n",ans); return ans;}int main(){ // freopen("sample.txt","r",stdin); int kase = 1 , T; scanf("%d",&T); while (T--) { scanf("%d",&N); for (int i = 0; i < N; i++) for (int j = 0 ; j < N; j++) scanf("%d",&res[i][j]); int ans = INF; for (int s = 0 ; s < 1<<N; s++) { bool flag = false; int tmp = 0; memset(ty,0,sizeof(ty)); for (int i = 0 ; i < N; i++) { if(((s & (1 << i)) == 0) && res[0][N - 1 - i]) { flag = true; break; } if ((s & (1 << i)) && res[0][N - 1 - i] == 0) { tmp++; ty[0][N- 1 - i] = 1; } if ((s & (1 << i)) && res[0][N - 1 - i]) ty[0][N - 1 -i] = 1; } if (flag) continue; //printf("%d\n",s); //for (int i = 0; i < N ; i++) printf("%d ",ty[0][i]); tmp = getans(s,tmp); ans = min(ans,tmp); } if (ans == INF) ans = -1; printf("Case %d: %d\n",kase++,ans); } return 0;}
UVA 11464 Even Parity
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。