체커 슬라이드

Checker Slide는 체커판 위에서 체커를 움직이는 퍼즐이다. 이 문제에서는 $6\times6$ 판에 체커 4개를 사용한다. 한 번의 이동은 체커 하나를 골라 판의 가장자리나 다른 체커에 닿을 때까지 왼쪽, 오른쪽, 위, 아래 중 한 방향으로 미는 것이다. 퍼즐의 목표는 주어진 시작 배치에서 주어진 끝 배치로 가는 이동 순서를 찾는 것이다. 다음은 배치 예시 몇 가지이다.

예를 들어 배치 1은 아래쪽 체커 두 개를 위쪽 체커 바로 아래까지 올린 다음, 오른쪽에 있는 체커를 왼쪽으로 옮기면 배치 2가 된다.

배치 3은 어떤 체커도 가장자리나 다른 체커에 인접하지 않으므로 비어 있지 않은 이동 순서의 끝 배치가 될 수 없다.

배치 1을 배치 4로 옮기는 한 방법은 다음과 같다.

주어진 시작 배치에서 주어진 끝 배치로 가는 데 필요한 최소 이동 횟수 N을 구하는 프로그램을 작성하시오. 이 문제에서는 각 문제 인스턴스에 해가 적어도 하나 존재한다고 보장한다.

입력은 두 줄로 이루어진다. 각 줄에는 공백 하나로 구분된 십진 정수 8개가 주어진다. 각 값은 $0 \le \text{value} \le 5$이며, 배치에 있는 체커 4개의 행과 열을 나타낸다. 순서는 ROW1 COLUMN1 ROW2 COLUMN2 ROW3 COLUMN3 ROW4 COLUMN4이다. 첫째 줄에는 시작 배치의 각 체커 위치가, 둘째 줄에는 끝 배치의 각 체커 위치가 주어진다.

첫째 줄에 문제를 푸는 최소 이동 횟수 N을 십진 정수 하나로 출력한다. 이어서 N개 줄에 각각 다음 체커 이동을 설명한다. 각 줄에는 그 단계에서 움직이는 체커의 시작 행, 시작 열, 끝 행, 끝 열을 나타내는 십진 정수 네 개를 공백으로 구분하여 출력한다.