UVA 11464 暴力+位运算 ***

题意：给你一个 n * n 的 01 矩阵，现在你的任务是将这个矩阵中尽量少的 0 转化为 1 ，使得每个数的上下左右四个相邻的数加起来是偶数。求最少的转化个数。

新风格代码

lrj书上说的很清楚了，就是判断下一行的代码有点冗余了，但是很好理解，就是模拟每位有的数字之和，然后判断未知为应该填的数字

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 #include<map>
  8 using namespace std;
  9 #define MOD 1000000007
 10 const int INF=0x3f3f3f3f;
 11 const double eps=1e-5;
 12 typedef long long ll;
 13 #define cl(a) memset(a,0,sizeof(a))
 14 #define ts printf("
*****
");
 15 #define sc(a) scanf("%d",&a);
 16 #define pt(a) printf("%d
",a);
 17 const int MAXN=25;
 18 
 19 //define single variable
 20 
 21 int n,m,tt;
 22 int ans,sum,sum1,sum2,tot,Max;
 23 
 24 
 25 //define arrays
 26 int a[MAXN][MAXN],b[MAXN][MAXN];
 27 char s[MAXN];
 28 int vis[MAXN];
 29 //define struct
 30 struct Node
 31 {
 32     int x,y;
 33     Node(){}
 34     /*Node(int xx,int yy,int tt)
 35     {
 36 
 37     }*/
 38     void in()
 39     {
 40         scanf("%d%d",&x,&y);
 41     }
 42 }node[MAXN];
 43 
 44 //others
 45 bool cmp(Node a,Node b)
 46 {
 47     return a.y>b.y;
 48 }
 49 
 50 void init()
 51 {
 52     ans=INF,sum=0,sum1=0,sum2=0,tot=0,Max=0;
 53     //cl(vis);
 54     //cl(node);
 55     cl(a),cl(b);
 56 }
 57 
 58 int check(int st)
 59 {
 60     //printf("st:  %d
",st);
 61     cl(b);
 62     int w=0;
 63     int i,j,k;
 64     for(i=0;i<n;i++)
 65     {
 66         if(st&(1<<i))
 67         {
 68             b[0][i]=1;
 69         }
 70         else b[0][i]=0;
 71     }
 72     /*for(i=0;i<n;i++)
 73     {
 74         printf("%d ",b[0][i]);
 75     }
 76     printf("
");*/
 77     for(i=0;i<n;i++)
 78     {
 79         for(j=0;j<n;j++)
 80         {
 81             if(a[i][j]==1&&b[i][j]==0)     return INF;  //注意只能由0变成1，不能从1变成0
 82             w=0;
 83             if(i==0)    //在顶层
 84             {
 85                 if(j==0)    //在顶层左上角
 86                 {
 87                     w=b[i][j+1];
 88                 }
 89                 else if(j==n-1) //顶层右上角
 90                 {
 91                     w=b[i][j-1];
 92                 }
 93                 else w=b[i][j-1]+b[i][j+1];
 94             }
 95             else if(i==n-1)
 96             {
 97                 if(j==0)
 98                 {
 99                     w=b[i][j+1]+b[i-1][j];
100                 }
101                 else if(j==n-1)
102                 {
103                     w=b[i-1][j]+b[i][j-1];
104                 }
105                 else w=b[i-1][j]+b[i][j+1]+b[i][j-1];
106                 if(w%2!=0)  return INF;
107             }
108             else
109             {
110                 if(j==0)
111                 {
112                     w=b[i-1][j]+b[i][j+1];
113                 }
114                 else if(j==n-1)
115                 {
116                     w=b[i-1][j]+b[i][j-1];
117                 }
118                 else
119                 {
120                     w=b[i-1][j]+b[i][j-1]+b[i][j+1];
121                 }
122             }
123             b[i+1][j]=w%2==0?0:1;
124         }
125     }
126     /*ts
127     for(i=0;i<n;i++)
128     {
129         for(j=0;j<n;j++)
130         {
131             printf("%d ",b[i][j]);
132         }
133         printf("
");
134     }
135     ts*/
136     int cnt=0;
137     for(i=0;i<n;i++)
138     for(j=0;j<n;j++)
139     {
140         if(a[i][j]!=b[i][j])    cnt++;
141     }
142     return cnt;
143 }
144 
145 int main()
146 {
147     int i,j,k,ca=1;
148     #ifndef ONLINE_JUDGE
149     freopen("1.in","r",stdin);
150     #endif
151 
152     scanf("%d",&tt);
153     while(tt--)
154     {
155         printf("Case %d: ",ca++);
156         init();
157         sc(n)
158         for(i=0;i<n;i++)
159             for(j=0;j<n;j++)
160                 sc(a[i][j])
161         for(i=0;i<(1<<n);i++)
162         {
163             ans=min(ans,check(i));
164         }
165         if(ans==INF)    ans=-1;
166         pt(ans)
167     }
168 }