퍼즐

3x3 표에는 0부터 8까지의 수가 한 칸에 하나씩 들어 있다. 0은 빈칸을 뜻한다. 목표 상태는 다음과 같다.

한 번의 이동에서는 빈칸과 상하좌우로 인접한 숫자 하나를 맞바꿀 수 있다. 표 밖으로 이동할 수는 없다.

초기 상태가 주어졌을 때, 목표 상태로 만들기 위한 최소 이동 횟수를 구하시오.

현재 표의 상태가 세 줄에 걸쳐 주어진다. 각 줄에는 공백으로 구분된 정수 세 개가 주어진다. 빈칸은 0으로 표시되며, 0부터 8까지의 수가 각각 한 번씩 등장한다.

목표 상태까지 필요한 최소 이동 횟수를 출력한다. 목표 상태로 만들 수 없으면 -1을 출력한다.