시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB107544956.322%

문제

삼각형 모양의 블록 피라미드를 가지고 노는 아기 팬더

$3$가지 색상의 블록으로 이루어진 블록 피라미드가 있다. 피라미드는 $N$행으로 이루어져 있고, $i\ (1 \le i \le N)$행은 $i$개의 블록으로 이루어져 있다.

또한, $i$행의 $j$번째 블록을 $(i, j)$로 표현했을 때, $(i, j)$는 아래와 같은 조건에 의해 최대 $6$개의 다른 블록과 맞닿아 있다.

  • $i \ge 2$ 이고 $j \ge 2$ 라면, $(i - 1, j - 1)$와 맞닿아 있다.
  • $i \ge 2$ 이고 $j \le i - 1$ 라면, $(i - 1, j)$와 맞닿아 있다.
  • $j \ge 2$ 라면, $(i, j - 1)$와 맞닿아 있다.
  • $j \le i - 1$ 라면, $(i, j + 1)$와 맞닿아 있다.
  • $i \le N - 1$ 라면, $(i + 1, j)$, $(i + 1, j + 1)$와 맞닿아 있다.

당신은 아름다운 블록 피라미드를 만들기 위해, 피라미드의 맞닿아 있는 블록의 색상이 같은 경우가 없도록 블록들을 재배치하고 싶다. 당신이 할 수 있는 연산은 아래 한 가지 뿐이다.

  • $i\ (2 \le i \le N)$행의 블록 $2$개를 골라 교환한다.

이 때, 목표를 이루기 위한 연산 사용 횟수의 최솟값을 출력하라.

입력

첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 1\,000)$

두 번째 줄부터 $N$개의 줄에 걸쳐 블록 피라미드의 각 행의 상태가 주어진다. $i + 1$번째 줄에는 블록 피라미드의 $i$행을 이루는 블록 $i$개의 색상 정보가 공백을 사이에 두고 주어진다. 색상 정보는 $0$, $1$ 또는 $2$의 정수이며, 각각 $3$가지의 다른 색상을 표현한다.

출력

피라미드의 맞닿아 있는 블록의 색깔이 같은 경우가 없도록 하기 위한 연산 사용 횟수의 최솟값을 출력하라. 해당 연산만으로 목표를 이루는 것이 불가능하다면 -1을 출력하라.

예제 입력 1

3
0
1 2
0 1 2

예제 출력 1

2

$3$행을 $[2,0,1]$로 바꾸는 방법과, $2$행을 $[2,1]$로 바꾸고 $3$행을 $[1,0,2]$로 바꾸는 방법이 있다.

예제 입력 2

4
0
1 2
1 0 2
1 2 0 0

예제 출력 2

2

예제 1 설명

예제 입력 3

2
0
1 1

예제 출력 3

-1