#P1391. 方阵安排

方阵安排

题目描述

A 班希望在学校的行军比赛中取得一个好成绩,他们希望自己班级的行军方阵是一个完美的方阵。他们认为,如果每个人四周的男生个数为偶数,那么这就是一个完美的方阵。

现在你已知道 A 班现有的方阵,你需要把尽量少的女生改成男生,使这个方阵变成一个完美的方阵。

输入格式

输入的第一行是一个正整数 nn,表示方阵大小为 n×nn \times n

22 到第 (n+1)(n+1) 行,每行 nn 个数非零即一的数字,第 (i+1)(i + 1) 行的第 jj 个数字代表方阵第 ii 行第 jj 列的人的性别,其中 00 为女生,11 为男生。

输出格式

输出一个数,表示最少需要把女生改成男生的个数。若无解,输出 1-1

3
0 0 0
1 0 0
0 0 0
3

提示

输入输出样例 1 解释

将方阵改为

0 1 0
1 0 1
0 1 0

数据规模与约定

对于 40%40\% 的数据,保证 n6n \leq 6

对于 100%100\% 的数据,保证 1n181 \leq n \leq 18