方阵安排
题目描述
A 班希望在学校的行军比赛中取得一个好成绩,他们希望自己班级的行军方阵是一个完美的方阵。他们认为,如果每个人四周的男生个数为偶数,那么这就是一个完美的方阵。
现在你已知道 A 班现有的方阵,你需要把尽量少的女生改成男生,使这个方阵变成一个完美的方阵。
输入输出格式
输入格式
输入的第一行是一个正整数 $n$,表示方阵大小为 $n \times n$ 。
第 $2$ 到第 $(n+1)$ 行,每行 $n$ 个数非零即一的数字,第 $(i + 1)$ 行的第 $j$ 个数字代表方阵第 $i$ 行第 $j$ 列的人的性别,其中 $0$ 为女生,$1$ 为男生。
输出格式
输出一个数,表示最少需要把女生改成男生的个数。若无解,输出 $-1$。
输入输出样例
输入样例 #1
3
0 0 0
1 0 0
0 0 0
输出样例 #1
3
说明
#### 输入输出样例 1 解释
将方阵改为
```
0 1 0
1 0 1
0 1 0
```
---
#### 数据规模与约定
对于 $40\%$ 的数据,保证 $n \leq 6$。
对于 $100\%$ 的数据,保证 $1 \leq n \leq 18$。