Turning off every lamp

Time limit4sMemory limit512 MB

Summary

Given an N x N grid of lamps, pressing a cell toggles it and its orthogonal neighbors; find the minimum number of presses that turns all lamps off, or -1 if impossible.

Level: Hard8 of 10
Topics: Bit manipulation, Brute force, Greedy, Simulation
Solved: No attempts yet

Problem

Hongik has an N x N lamp board. Every cell of the board carries one lamp, and each lamp is either on or off. Pressing the lamp in a cell flips that lamp together with the lamps directly above, below, left of, and right of it, so up to five lamps change at once. A lamp that was on turns off, and a lamp that was off turns on. Rows are numbered 1 to N from top to bottom, and columns are numbered 1 to N from left to right.

Take the board in Figure 1. A 0 means the lamp is off, and a 1 means the lamp is on.

The starting board

Figure 1

Pressing the lamp at (2, 2) in Figure 1, shown in gray, changes the board into Figure 2.

The board after pressing (2, 2)

Figure 2

For another example, press the lamp at (1, 1) in Figure 3.

Another starting board

Figure 3

The board becomes Figure 4.

The board after pressing (1, 1)

Figure 4

Cell (1, 1) has no neighbor above it and no neighbor to its left. Only that lamp and the lamps to its right and below it change.

The order of the presses does not change the result, and pressing the same lamp twice restores the board to its earlier state.

Hongik wants to turn off every lamp on the board. Given the starting board, find the minimum number of presses B that turns every lamp off. If no sequence of presses turns every lamp off, print -1.

Input

The first line contains the board size N.

Each of the next N lines contains N values, either 0 or 1, separated by spaces. The $j$ -th value on the $i$ -th line is 1 when the lamp at $(i, j)$ is on and 0 when it is off.

$2 \le N \le 18$

Output

Print the minimum number of presses B that turns every lamp off, on one line. If no sequence of presses turns every lamp off, print -1.

Examples3

Example 1
Input
```
2
1 1
1 1
```
Expected output
```
4
```
Example 2
Input
```
3
0 0 0
0 0 0
0 0 1
```
Expected output
```
5
```

Example 3

Input

Expected output

-1