首页 > 代码库 > 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