25568번 - 피라미드

$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을 출력하라.