uva------(11464)Even Parity

D

Even Parity Input: Standard Input Output: Standard Output

We have a grid of size N x N. Each cell of the grid initially contains a zero(0) or a one(1).  The parity of a cell is the number of 1s surrounding that cell. A cell is surrounded by at most 4 cells (top, bottom, left, right).

Suppose we have a grid of size 4 x 4: 

1

0

1

0

The parity of each cell would be

1

3

1

2

1

1

1

1

2

3

3

1

0

1

0

0

2

1

2

1

0

0

0

0

0

1

0

0

For this problem, you have to change some of the 0s to 1s so that the parity of every cell becomes even. We are interested in the minimum number of transformations of 0 to 1 that is needed to achieve the desired requirement.

Input

The first line of input is an integer T (T<30) that indicates the number of test cases. Each case starts with a positive integer N(1≤N≤15). Each of the next N lines contain N integers (0/1) each. The integers are separated by a single space character.

Output

For each case, output the case number followed by the minimum number of transformations required. If it's impossible to achieve the desired result, then output -1 instead.

Sample Input                             Output for Sample Input

3 3 0 0 0 0 0 0 0 0 0 3 0 0 0 1 0 0 0 0 0 3 1 1 1 1 1 1 0 0 0

Case 1: 0 Case 2: 3 Case 3: -1


Problem Setter: Sohel Hafiz,

Special Thanks: Derek Kisman, Md. Arifuzzaman Arif

代码

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn = 20;
 6 const int INF = 1000000000;
 7 int n,A[maxn][maxn],B[maxn][maxn];
 8 
 9 int work(int s)
10 {
11     memset(B,0,sizeof(B));
12     for(int c=0 ; c<n;c++)
13     {
14         if(s&(1<<c))B[0][c]=1;
15         else if(A[0][c]==1) return INF;
16     }
17     for(int r=1;r<n ;r++)
18     {
19         for(int c=0;c<n;c++)
20         {
21           int sum=0;
22           if(r>1)sum+=B[r-2][c];
23           if(c>0)sum+=B[r-1][c-1];
24           if(c<n-1) sum+=B[r-1][c+1];
25           B[r][c]=sum%2;
26           if(A[r][c]==1&&B[r][c]==0)
27             return INF;
28         }
29     }
30     int cnt=0;
31     for(int r=0;r<n;r++)
32     {
33         for(int c=0;c<n;c++)
34         {
35           if(A[r][c]!=B[r][c])cnt++;
36         }
37     }
38     return cnt;
39 }
40 int main()
41 {
42     int T;
43     scanf("%d",&T);
44     for(int kase=1;kase<=T;kase++)
45     {
46         scanf("%d",&n);
47         for(int r=0;r<n;r++)
48         {
49             for(int c=0;c<n;c++)
50             {
51                 scanf("%d",&A[r][c]);
52             }
53         }
54         int ans=INF;
55         for(int s=0;s<(1<<n);s++)
56             ans=min(ans,work(s));
57         if(ans==INF) ans=-1;
58         printf("Case %d: %d\n",kase,ans);
59 
60     }
61     return 0;
62 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏進无尽的文章

编码篇 - 正则表达式及其相关

有时我们需要在一大段长文本中过滤出我们需要的字段,或者检验该文本是否符合要求(该文本是否是邮箱,链接,电话号码或身份证),这时候就需要用到正则表达式了,当然我们...

12520
来自专栏ml

HDUOJ-------1753大明A+B(大数之小数加法)

大明A+B Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

362120
来自专栏java初学

spring框架(3)— spring集合类的注入

374130
来自专栏码匠的流水账

聊聊flink的PartitionableListState

flink-runtime_2.11-1.7.0-sources.jar!/org/apache/flink/runtime/state/DefaultOper...

15040
来自专栏小樱的经验随笔

HDU 2034 人见人爱A-B

人见人爱A-B Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (J...

344100
来自专栏微信公众号:Java团长

Java中的十个&quot;单行代码编程&quot;(One Liner)

本文列举了十个使用一行代码即可独立完成(不依赖其他代码)的业务逻辑,主要依赖的是Java8中的Lambda和Stream等新特性以及try-with-resou...

11320
来自专栏友弟技术工作室

golang之Struct什么是结构体struct?

最近在复习golang,学习的东西,如果不使用,很快就会忘记。所以,准备复习完golang,做一个练手的小项目,加深对golang的学习。今天开始公司,进入封闭...

62160
来自专栏算法修养

UESTC 482 Charitable Exchange(优先队列+bfs)

Charitable Exchange Time Limit: 4000/2000MS (Java/Others)     Memory Limit: 65...

34550
来自专栏null的专栏

剑指Offer——编程题的Java实现

声明:我写这个的意图是我在看书的过程中,就我掌握的内容做一个笔记,没有抄袭的意图。再次说明一下,我找工作的过程中并不顺利,没有像那些牛人们拿到一大把的Offer...

95830
来自专栏算法修养

POJ-2329 Nearest number - 2(BFS)

Nearest number - 2 Time Limit: 5000MS Memory Limit: 65536K Total Submis...

25040

扫码关注云+社区

领取腾讯云代金券