华师一附中OI组

标题: P1391 方阵安排 [打印本页]

作者: admin 时间: 2018-5-17 13:13
标题: P1391 方阵安排
https://www.luogu.org/problemnew/show/P1391

题目描述
A班希望在学校的行军比赛中取得一个好成绩，他们希望自己班级的行军方阵是一个完美的方阵。他们认为，如果每个人四周的男生个数为偶数，那么这就是一个完美的方阵。现在你已知道A班现有的方阵，你需要把尽量少的女生改成男生，使这个方阵变成一个完美的方阵。

输入输出格式
输入格式：
第1行，一个正整数n，表示方阵大小为n*n的。

第2~n+1行，每行n个数，代表方阵中的人（0为女生，1为男生）。

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

输入输出样例
输入样例#1：
3
0 0 0
1 0 0
0 0 0
输出样例#1：
3
说明
对样例的说明：

将方阵改为：0 1 0

1 0 1 0 1 0 即可。

数据范围：

对于40%的数据，n≤6

对于100%的数据，n≤18

欢迎光临华师一附中OI组 (http://hsyit.cn/)