Problem1168--PIPI的方格

1168: PIPI的方格

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 546  Solved: 340
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI有一个N*N的方格,每个格子中有一个数字(0或者1),PIPI可以使任意格子中的0变成1,现在它想让每个格子的上下左右相邻格子中数字之和为偶数。
请你告诉PIPI,最少使用几次操作(将0变成1),才能使每个格子的上下左右(如果存在)相邻数字和为偶数。

Input

多组数据
第一行为一个正整数n,n<=15
接下来n行,每行n个数字(0或者1)。

Output

对于每组数据,输出一个整数,代表最少需要多少次操作。
若无解,输出-1.

Sample Input

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

0
3
-1

Source/Category