전구 끄기

시간 제한4초메모리 제한512 MB

요약

N x N 격자의 램프에서 한 칸을 누르면 그 칸과 상하좌우 이웃이 함께 켜지거나 꺼질 때, 모든 램프를 끄는 최소 누름 횟수를 구하고 불가능하면 -1을 출력한다.

난이도: 어려움10점 중 8점
유형: 비트 연산, 완전 탐색, 그리디, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

홍익이는 N x N 크기의 전구 판을 가지고 있다. 판의 각 칸에는 전구가 하나씩 달려 있고, 각 전구는 켜져 있거나 꺼져 있다. 어떤 칸의 전구를 누르면 그 전구와 상하좌우로 인접한 전구까지 최대 5개의 상태가 한꺼번에 바뀐다. 켜져 있던 전구는 꺼지고, 꺼져 있던 전구는 켜진다. 행은 위에서 아래로 1번부터 N번까지, 열은 왼쪽에서 오른쪽으로 1번부터 N번까지 번호를 매긴다.

<그림 1> 같은 전구 판이 있다고 하자. 0은 전구가 꺼져 있다는 뜻이고, 1은 켜져 있다는 뜻이다.

전구 판의 처음 상태

<그림 1>

<그림 1>에서 회색으로 표시한 (2, 2) 전구를 누르면 판은 <그림 2>처럼 바뀐다.

(2, 2)를 누른 뒤의 전구 판

<그림 2>

다른 예로 <그림 3>에서 (1, 1) 전구를 누르면

또 다른 전구 판의 처음 상태

<그림 3>

판은 <그림 4>처럼 바뀐다.

(1, 1)을 누른 뒤의 전구 판

<그림 4>

(1, 1)에는 위쪽과 왼쪽에 이웃한 칸이 없다. 그래서 자기 자신과 오른쪽, 아래쪽 전구만 상태가 바뀐다.

누르는 순서는 결과를 바꾸지 않고, 같은 전구를 두 번 누르면 판은 처음 상태로 돌아온다.

홍익이는 판의 전구를 모두 끄고 싶다. 처음 상태가 주어질 때 모든 전구를 끄는 데 필요한 최소 누름 횟수 B를 구하여라. 모두 끄는 방법이 없으면 -1을 출력한다.

입력

첫째 줄에 전구 판의 크기 N이 주어진다.

이어지는 N개의 줄에는 줄마다 0 또는 1이 N개씩 공백으로 구분되어 주어진다. $i$ 번째 줄의 $j$ 번째 수는 $(i, j)$ 칸의 전구가 켜져 있으면 1, 꺼져 있으면 0이다.

$2 \le N \le 18$

출력

모든 전구를 끄는 데 필요한 최소 누름 횟수 B를 한 줄에 출력한다. 모든 전구를 끄는 방법이 없으면 -1을 출력한다.

예제3

예제 1
입력
```
2
1 1
1 1
```
예상 출력
```
4
```
예제 2
입력
```
3
0 0 0
0 0 0
0 0 1
```
예상 출력
```
5
```

예제 3

입력

예상 출력

-1