BOJ 18529 Hopscotch 50

문제 링크:

문제 내용

$n \times n$의 사각 격자의 각 칸에 1 이상 $k$ 이하의 정수가 쓰여 있습니다. 당신은 이 격자 위에서 Hopscotch 놀이를 하려고 합니다. Hopscotch는 다음과 같은 과정으로 이루어집니다.

• 먼저 1이 쓰여 있는 칸 중 하나를 밟습니다.
• 현재 밟은 수가 $x$일 때, $x+1$이 쓰여 있는 칸 중 하나로 점프합니다. 이를 $k$가 쓰여 있는 칸을 밟을 때까지 반복합니다.

$(x_1, y_1)$에서 $(x_2, y_2)$로 점프할 때 필요한 에너지는 $|x_1 - x_2| + |y_1 - y_2|$입니다. Hopscotch를 하는 방법이 존재한다면, 필요한 에너지의 합의 최솟값을 출력하세요.

입력

첫 번째 줄에 $n$과 $k$가 주어집니다. ($1 \le n \le 50$, $1 \le k \le n^2$)

다음 $n$줄에 걸쳐서 사각 격자가 주어집니다.

출력

주어진 입력에서 Hopscotch를 할 수 있다면, 필요한 에너지의 합의 최솟값을 출력합니다. 그것이 불가능하다면, -1을 대신 출력합니다.

문제 풀이