Trên một bàn cờ kích thước có quân cờ đen và quân cờ trắng. Hai ô được coi là liền kề khi và chỉ khi chúng có chung một cạnh. Quy tắc di chuyển quân cờ là đổi chỗ hai quân cờ nằm ở hai ô liền kề.
Cho một trạng thái bàn cờ ban đầu và một trạng thái bàn cờ đích, hãy tìm một chuỗi di chuyển ngắn nhất để biến đổi bàn cờ từ trạng thái ban đầu sang trạng thái đích.
Dữ liệu:
Bốn dòng đầu tiên, mỗi dòng chứa con số ( hoặc , đại diện cho đen hoặc trắng), mô tả trạng thái bàn cờ ban đầu.
Tiếp theo là một dòng trống.
Từ dòng thứ sáu đến dòng thứ chín, mỗi dòng chứa con số ( hoặc ), mô tả trạng thái bàn cờ đích.
Kết quả:
Dòng đầu tiên của file kết quả chứa một số nguyên , biểu thị số bước di chuyển ít nhất.
