Informatica Online Judge

  8-Puzzle [0608 / 0260]

Time Limit(Test case) : 5000(ms)
Number of users who solved : 111   Total Tried : 153


The Champion of this Problem (C++) : gs140742 - 0ms / 872byte
My Best Submission (C++) : N/A

[]

Background

n-puzzle는 잘 알려진 유명한 퍼즐이다.

그 중에서 3*3으로 이루어진 퍼즐을 8퍼즐이라고 한다.

8퍼즐의 초기 상태는 다음과 같다.





위 그림에서 공백 칸으로 다른 숫자판을 옮길 수 있다.

만약 다음과 같은 상태의 숫자판이 주어졌다면 초기상태로 만드는 것을 퍼즐을 푼다. 라고 한다.

아래 그림은 한 퍼즐을 풀어가는 예이다.





퍼즐의 상태가 주어졌을 때, 퍼즐을 초기상태로 만드는 최소 이동 횟수를 구하는 프로그램을 작성하시오.

단, 풀수 없는 상태의 퍼즐일 경우에는 -1을 출력한다.

Input

3행에 걸쳐서 3개의 숫자가 공백으로 구분되어 입력된다.
(단, 0은 공백칸을 의미한다.)

Output

최소 이동횟수를 출력한다. 단 퍼즐을 해결할 수 없다면 -1을 출력한다.
(풀 수 있는 퍼즐이라면 20번 이내로 해결 할 수 있는 예시가 주어진다.)

IO Example

입력
1 2 3
4 0 5
7 8 6

출력
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]