Rush Hour 퍼즐

Rush Hour는 Nob Yoshigahara가 1970년대에 만든 퍼즐 게임이다. 현재는 ThinkFun이 제조한다. 보드는 6 × 6 격자이며, 차량이 미끄러지도록 타일에 홈이 파여 있다. 자동차와 트럭은 모두 폭이 한 칸이다. 자동차는 길이가 두 칸, 트럭은 길이가 세 칸이다. 차량은 직선을 따라 앞뒤로만 움직일 수 있다. 목표는 다른 차량을 길에서 치워서, 유일한 빨간 자동차를 보드의 출구로 완전히 빼내는 것이다. 그림 1은 예시 퍼즐이다.

그림 1: Rush Hour 퍼즐의 예.

각 차량에는 1부터 차량 수까지의 고유한 id가 붙는다. 빨간 자동차의 id는 1이다. 보드는 6 × 6 행렬로 나타내며, 이를 보드 행렬이라고 한다. 각 원소는 그 칸에 있는 차량의 id이고, 차량이 없으면 0이다. 출구는 3행의 오른쪽 끝에 있다. 그림 2는 그림 1 퍼즐의 보드 행렬이다.

그림 2: 그림 1 퍼즐에 대응하는 보드 행렬.

차량(자동차 또는 트럭)을 한 칸 옮기는 것을 한 스텝이라고 한다. 10스텝 이하로 풀 수 있는 퍼즐을 쉬운 퍼즐이라고 한다. 즉 빨간 자동차가 출구로 완전히 빠져나갈 수 있으면 쉬운 퍼즐이다. 퍼즐이 쉬운지 판별하는 프로그램을 작성하라.

입력은 6줄이다. 각 줄에는 보드 행렬의 한 행을 나타내는 정수 6개가 공백으로 구분되어 있다.

퍼즐이 쉬우면 풀이에 필요한 최소 스텝 수를 출력한다. 그렇지 않으면 -1을 출력한다.

각 퍼즐의 보드에 있는 차량은 최대 10대이다.

각 퍼즐에서 보드 밖으로 뺄 수 있는 것은 빨간 자동차뿐이다.