UVA - 11464 偶数矩阵(模拟,枚举)

2017年04月20日 13点热度 0人点赞 0条评论
现在有一个n*n的01矩阵(也就是说里面的每个数要么是1,要么是0),你的任务是通过把一些0变成1,使得每个元素的上下左右的元素(如果存在的话)之和均为偶数。例如,下面的4*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

现在,你的任务是计算出最少需要变换多少个0,才能使得矩阵中每个元素上下左右(如果存在的话)的元素加起来之和是偶数。

例如:
0 0 0             0 1 0
1 0 0             1 0 1
0 0 0变化为 0 1 0

 

Input

输入的第一行为测试数据的数量t(t<=30),每组数组的第一行是一个正整数n(1<=n<=15),接下来的n行,每行包含n个非0即1的整数,相邻整数之间用一个空格隔开。

Output

对于每组数组,输出被改变的0的最少数量,如果无解,输出-1。

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

Sample Output

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

Hint

C题输出格式注意:Case@x:@y x和y是数,@是空格

//思路:枚举第一行的数,有2^15=32768种可能,其他行的数可以通过第一行的数算出 
//时间复杂度2^n*n*n 
#include
#include
#include
using namespace std;
const int maxn=20;
const int INF=0x3f3f3f3f;
int n,a[maxn][maxn],b[maxn][maxn];
int main(){
	int T;
	scanf("%d",&T);
	for(int k=1;k<=T;k++){
		int ans=INF;
		memset(b,0,sizeof(b));//这个初始化一开始忘记了,gg 
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		scanf("%d",&a[i][j]);
		for(int s=0;s<(1<>(i-1))&1;
				if(b[1][i]==0&&a[1][i]) goto End;
				if(b[1][i]!=a[1][i]) cnt++;
			}
			for(int i=2;i<=n;i++)
			for(int j=1;j<=n;j++){
				b[i][j]=(b[i-1][j-1]+b[i-1][j+1]+b[i-2][j])%2;
				if(b[i][j]!=a[i][j]) cnt++;
				if(b[i][j]==0&&a[i][j]||cnt>ans) goto End;
			}
			ans=min(ans,cnt);
			End:;
		}
		if(ans==INF) ans=-1;
		printf("Case %d: %dn",k,ans);
	}
	return 0;
}
未经允许不得转载!UVA - 11464 偶数矩阵(模拟,枚举)

update

纸上得来终觉浅, 绝知此事须躬行。