2994: 偶数矩阵[Even Parity,UVA11464]
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 0 Solved: 0
[Status] [Submit] [Creator:]
Description
我们有一个N*N的矩阵，矩阵的每个单元都有一个数字（非0即1）。环绕每个单元格的上、下、左、右的四个单元的和叫做这个单元格的“奇偶性”。
例如，下图是一个4*4的矩阵：
你的任务是把单元格里面的0变成1，或者把1变成0，使得每个单元格的“奇偶性”是偶数（即使得每个单元格的上、下、左、右的和是偶数），而且尽可能让改变的单元格的个数最少。
例如下图把图a所示的矩阵变成图b所示的矩阵，至少需要把3个0变成1，才能保证是偶数矩阵。
例如，下图是一个4*4的矩阵：
你的任务是把单元格里面的0变成1，或者把1变成0，使得每个单元格的“奇偶性”是偶数（即使得每个单元格的上、下、左、右的和是偶数），而且尽可能让改变的单元格的个数最少。
例如下图把图a所示的矩阵变成图b所示的矩阵，至少需要把3个0变成1，才能保证是偶数矩阵。
Input
第一行，一个整数T（0＜T＜30），表示数据组数
每组数据，第一行，一个整数N，表示是N*N的矩阵
接下来N行，每行N个用空格隔开的非0即1的整数，描述矩阵。
每组数据，第一行，一个整数N，表示是N*N的矩阵
接下来N行，每行N个用空格隔开的非0即1的整数，描述矩阵。
Output
参考输出样例，对于每组数据，输出一个整数，表示被改变的单元格的最少个数。如果无解，输出-1
Sample Input Copy
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 Copy
Case 1: 0
Case 2: 3
Case 3: -1