Even Parity

题意翻译

给你一个 $n \times n$ 的 $01$ 矩阵(每个元素非 $0$ 即 $1$),你的任务是把尽量少的 $0$ 变成 $1$,使得原矩阵便为偶数矩阵(矩阵中每个元素的上、下、左、右的元素(如果存在的话)之和均为偶数)。 ### 输入格式 输入的第一行为数据组数 $T$($T \le 30$)。每组数据:第一行为正整数 $n$($1 \le n \le 15$);接下来的 $n$ 行每行包含 $n$ 个非 $0$ 即 $1$ 的整数,相邻整数间用一个空格隔开。 ### 输出格式 对于每组数据,输出被改变的元素的最小个数。如果无解,输出 $-1$。

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2459 [PDF](https://uva.onlinejudge.org/external/114/p11464.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11464/bceb7090c748f3e4ff9ed8ca97fa3ecd7b635348.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11464/3e609d145c46b29d28dd750719dc5c46220e5054.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11464/6b28873de557f79199cab9492b93ce644840296a.png)

输入输出样例

输入样例 #1

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

输出样例 #1

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