RúnaHeimur

슬라이딩 퍼즐 — Wikipedia

Níels는 비디오 게임 RúnaHeimur의 엄청난 실력자다. 게임에서는 낚시, 나무 베기, 용과 싸우기, 모자 구매하기, 모험 떠나기, 퍼즐 두루마리 풀기처럼 서로 다른 많은 일을 할 수 있다. Níels는 이 모든 일을 즐기지만, 한 가지 이유로 퍼즐 두루마리만은 싫어한다. 퍼즐 두루마리에서는 때때로 슬라이딩 퍼즐을 풀어야 하는데, 그는 이를 몹시 지루하다고 생각한다. 그래서 그는 자신을 대신해 이 퍼즐들을 풀어 주는 프로그램을 작성해 달라고 부탁한다.

슬라이딩 퍼즐에서는 그림이 $n$개의 행과 $m$개의 열로 나뉜다. 따라서 그림을 이루는 칸은 모두 $n \cdot m$개다. 칸에는 흔히 왼쪽에서 오른쪽으로 $1$부터 $n \cdot m$까지의 수가 표시된다. 그러면 원래 상태는 예를 들어 다음과 같다.

1 2 3
4 5 6
7 8 9

그런 다음 칸을 움직일 공간을 만들기 위해 번호가 $n \cdot m$인 칸을 제거한다. 이후 그림이 뒤섞일 때까지 칸들을 무작위로 민다. 목표는 그림이 원래 모습대로 보이도록 칸들을 원래 위치로 옮기는 것이다.

각 게임 상태에서는 최대 네 가지 이동이 허용된다.

• 이동 U은 빈칸 바로 아래의 칸을 위로 옮긴다는 뜻이다.

• 이동 D은 빈칸 바로 위의 칸을 아래로 옮긴다는 뜻이다.

• 이동 L은 빈칸 바로 오른쪽의 칸을 왼쪽으로 옮긴다는 뜻이다.

• 이동 R은 빈칸 바로 왼쪽의 칸을 오른쪽으로 옮긴다는 뜻이다.

해당 이동에서 움직여야 하는 칸이 존재하지 않으면 그 이동은 그 게임 상태에서 불법이다.

점수

그룹 | 점수 | 제한

1 | 15 | $n = 2, m = 2$

2 | 15 | $n = 2, m \leq 3$

3 | 15 | $n = 2, m \leq 5$

4 | 5 | $n = 2, m \leq 10$

5 | 15 | $n \leq 3, m \leq 3$

6 | 15 | $n \leq 4, m \leq 4$

7 | 15 | $n \leq 5, m \leq 5$

8 | 5 | 추가 제한 없음

입력은 여러 줄로 주어진다. 첫째 줄에는 두 정수 $n$와 $m$ ($2 \leq n, m \leq 10$)가 주어지며, 여기서 $n$는 게임판의 행 수를, $m$는 열 수를 나타낸다. 다음 $n$개 줄에는 각각 $m$개의 정수가 주어진다. 수는 $1$부터 $n \cdot m$까지의 범위에 있으며, 각 수는 정확히 한 번씩 등장한다. 또한 수 $n \cdot m$은 항상 입력의 마지막 수다.

게임판을 완성된 상태로 만드는 이동들을 한 줄에 출력한다. 해답에 불법 이동이 포함되어 있으면 오답으로 판정된다. 해답이 존재하지 않으면 impossible을 출력한다. 해답이 존재한다면, $10\,000$번보다 적은 이동으로 이루어진 해답이 존재한다고 가정해도 된다.