Trong một khung hình vuông kích thước có đặt một số đồ chơi giống hệt nhau. Một người muốn sắp xếp lại các đồ chơi này thành một trạng thái lý tưởng trong tâm trí anh ta. Quy định rằng khi di chuyển, đồ chơi chỉ có thể được di chuyển sang 4 hướng: trên, dưới, trái, phải và vị trí di chuyển đến phải không có đồ chơi.
Hãy tính số lần di chuyển ít nhất để đưa các đồ chơi từ trạng thái ban đầu về trạng thái mục tiêu.
Dữ liệu:
Bốn dòng đầu tiên biểu diễn trạng thái ban đầu của đồ chơi, mỗi dòng gồm 4 số hoặc . Số biểu thị ô có đồ chơi, số biểu thị ô trống.
Tiếp theo là một dòng trống.
Bốn dòng tiếp theo biểu diễn trạng thái mục tiêu của đồ chơi, mỗi dòng gồm 4 số hoặc , ý nghĩa tương tự như trên.
Kết quả:
Một số nguyên duy nhất là số lần di chuyển ít nhất cần thiết.
