8-puzzle game
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