首页 > 代码库 > 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 偶数矩阵
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。