首页 > 代码库 > Uva 11464 偶数矩阵

Uva 11464 偶数矩阵

题目链接:https://uva.onlinejudge.org/external/114/11464.pdf

和开关问题类似,只不过现在是用的位运算操作更简单了,其中要注意的是,只能将0变成1.

 1 #include <bits/stdc++.h> 2  3 using namespace std; 4  5 #define inf 0x3f3f3f3f 6  7 int a[20][20]; 8 int b[20][20]; 9 int n;10 11 int dr[3] = {-1,0,0};12 int dc[3] = {0,-1,1};13 14 int sum(int di,int dj) {15     int ans = 0;16     for(int i=0;i<3;i++)17     {18         int dx = di + dr[i];19         int dy = dj + dc[i];20 21         if(dx>=0&&dx<n&&dy>=0&&dy<n)22             ans +=b[dx][dy];23     }24     return ans;25 }26 27 bool test(int i) {28     int x = sum(n-1,i);29     if(x%2)30         return false;31     else return true;32 }33 34 int check(int s) {35 36 37     for(int i=0;i<n;i++)38         if(s&(1<<i)) b[0][i] = 1;39         else b[0][i] = 0;40 41     for(int i=0;i<n-1;i++)42     {43         for(int j=0;j<n;j++) {44             int x = sum(i,j);45             if(x%2==0)46                 b[i+1][j] = 0;47             else b[i+1][j] = 1;48         }49     }50 51     for(int i=0;i<n;i++)52         if(!test(i))53         return inf;54 55     int ans = 0;56     for(int i=0;i<n;i++) {57         for(int j=0;j<n;j++)58         {59             if(a[i][j]==1&&b[i][j]==0)60                 return inf;61         }62     }63 64     for(int i=0;i<n;i++)65     {66         for(int j=0;j<n;j++)67             if(a[i][j]!=b[i][j])68                 ans++;69     }70     return ans;71 }72 73 int main()74 {75     int kase = 1,t;76     scanf("%d",&t);77     while(t--) {78 79         scanf("%d",&n);80 81         for(int i=0;i<n;i++)82             for(int j=0;j<n;j++)83                 scanf("%d",&a[i][j]);84 85         int ans = inf;86         for(int s=0;s<(1<<n);s++)87             ans = min(ans,check(s));88 89         printf("Case %d: ",kase++);90         if(ans==inf)91             printf("-1\n");92         else printf("%d\n",ans);93     }94     return 0;95 }

 

Uva 11464 偶数矩阵