8-puzzle game


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Phúc đang chơi trò chơi 8-puzzle. Cậu có một bảng 3×3 gồm 8 ô chứa các số từ 1 đến 8 và một ô trống (xem như ô đó mang giá trị là 0).

Mỗi bước, cậu có thể trượt một ô liền kề vào vị trí trống. Tức là thay đổi vị trí của ô chứa giá trị 0 với một trong các ô kề cạnh. Phúc sẽ thắng khi cậu đưa bảng về trạng thái sau:

1 2 3

4 5 6

7 8 0

Cho biết trạng thái ban đầu của bảng, hãy giúp Phúc tìm ra số bước ít nhất để chiến thắng trò chơi.

Dữ liệu

  • Gồm 3 dòng, mỗi dòng chứa 3 số nguyên là trạng thái ban đầu của bảng.

Kết quả

  • Kết quả bài toán. Nếu không thể thắng, in ra $-1$.

Ví dụ

Ví dụ 1

input

1 2 3
0 4 5
7 8 6

output

3

Comments

There are no comments at the moment.