P1391 Square Formation Arrangement

Class A wants a good result in the school marching competition, and they hope their class’s marching formation is a perfect square formation. They consider the formation perfect if, for every person, the number of boys among the four adjacent neighbors (up, down, left, right) is even, considering only neighbors within the grid. You are given Class A’s current formation. You need to change as few girls as possible into boys to make the formation perfect.

The first line contains a positive integer $n$, meaning the formation is of size $n \times n$. Lines $2$ to $(n+1)$ each contain $n$ numbers, each either $0$ or $1$. In the $(i+1)$-th line, the $j$-th number represents the gender of the person at row $i$, column $j$, where $0$ means girl and $1$ means boy.

Output a single number: the minimum number of girls that need to be changed into boys. If there is no solution, output $-1$.

#### Explanation for Sample 1 Change the formation to: ``` 0 1 0 1 0 1 0 1 0 ``` --- #### Constraints For $40\%$ of the testdata, $n \leq 6$. For $100\%$ of the testdata, $1 \leq n \leq 18$. Translated by ChatGPT 5