2014
02-27

# Uva-11464-Even Parity[模拟]

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

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

Output for Sample Input

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

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int INF = 1<<30;
const int MAXN = 20;
int m[MAXN][MAXN];

int solve(int n , int s){
int tmp[MAXN][MAXN];
memset(tmp , 0 , sizeof(tmp));
for(int i = 0 ; i < n ; i++){
if(s & (1<<i))//说明这一位是1
tmp[0][i] = 1;
else if(m[0][i] == 1)//这里得到的是0，但是实际上1不可能存在
return INF;
}
//求出tmp数组
for(int i = 1 ; i < n ; i++){
for(int j = 0 ; j < n ; j++){
int sum = 0;//通过前一行求出下一行
if(i > 1)//加上
sum += tmp[i-2][j];
if(j > 0)//加左
sum += tmp[i-1][j-1];
if(j < n-1)
sum += tmp[i-1][j+1];
//通过sum求出第tmp[i][j];
if(sum%2)//如果sum为奇数
tmp[i][j] = 1;
if(tmp[i][j] == 0 && m[i][j] == 1)//如果现在为0但是原先为1这种情况是不可能的
return INF;
}
}
//求出这次的变换的次数
int cnt = 0;
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n ; j++)
if(m[i][j] != tmp[i][j])
cnt++;
return cnt;
}

int main(){
int Case , n , cnt = 1;
scanf("%d" , &Case);
while(Case--){
scanf("%d" , &n);
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n ; j++)
scanf("%d" , &m[i][j]);
int ans = INF;
for(int i = 0 ; i < (1<<n) ; i++)//枚举第一行的状态
ans = min(ans , solve(n , i));//求最小的ans
printf("Case %d: %d\n" , cnt++ , ans == INF ? -1 : ans);
}
return 0;
}

1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

2. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。

3. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确