Push!!

Mr. Schwarz는 유명한 파워 프로 레슬러였다. 그는 창고지기 아르바이트를 시작한다. 그의 일은 창고의 벽과 기둥을 부수지 않으면서 화물을 반복해서 밀어 목표 지점으로 옮기는 것이다.

창고에는 기둥이 있을 수 있다. 기둥이 있는 곳을 제외하면 창고 바닥은 화물 크기에 맞는 정사각형 타일로 깔려 있다. 기둥 하나는 타일 하나와 같은 면적을 차지한다.

처음에 화물은 어떤 타일의 중앙에 있다. 한 번 밀면, 그는 적절한 위치에 있을 때 화물을 인접한 타일의 중앙으로 옮길 수 있다. 화물을 옮길 타일은 화물이 있는 타일에 인접한 (최대) 네 타일, 즉 동쪽, 서쪽, 북쪽, 남쪽 타일 중 하나여야 한다.

밀려면 그는 화물이 있는 타일에 인접한 타일 위에 있어야 한다. 그는 자신이 화물을 바라보는 방향과 같은 방향으로만 화물을 밀 수 있고, 당길 수는 없다. 따라서 화물이 벽이나 기둥 옆 타일에 있으면 그는 화물을 벽이나 기둥을 따라 움직일 수만 있다. 게다가 화물을 모서리 타일에 놓으면 더 이상 움직일 수 없다.

그는 화물과 기둥 같은 장애물이 가로막지 않는 경로가 있으면 위치를 바꿀 수 있다. 목표 지점은 장애물이 아니다. 또 그는 동쪽, 서쪽, 북쪽, 남쪽 네 방향으로만 이동할 수 있고, 방향은 타일의 중앙에서만 바꿀 수 있다.

그는 그렇게 젊지 않기 때문에 필요한 미는 횟수를 최소로 줄여 체력을 아끼려 한다. 그러나 걷기는 그에게 아주 가벼운 운동이므로 만보계 수치는 신경 쓰지 않는다.

당신의 일은 화물을 목표 지점으로 옮기는 데 필요한 최소 미는 횟수를 출력하는 프로그램을 작성하는 것이다. 옮길 수 없다면 그 사실을 출력해야 한다.

입력은 여러 개의 지도로 이루어지며, 각 지도는 창고의 크기와 배치를 나타낸다. 지도는 다음과 같은 형식으로 주어진다.

w h
d11 d12 d13 ··· d1w
d21 d22 d23 ··· d2w
...
dh1 dh2 dh3 ··· dhw

정수 w와 h는 창고 바닥 두 변의 길이를 바닥 타일의 너비 단위로 나타낸 것이다. w와 h는 7 이하다. 정수 dij는 해당 바닥 영역에 처음에 무엇이 있는지를 다음과 같이 나타낸다.

• 0: 아무것도 없음 (그냥 바닥 타일)
• 1: 기둥
• 2: 화물
• 3: 목표 지점
• 4: 창고지기 (Mr. Schwarz)

정수 2, 3, 4는 각각 지도에서 dij로 정확히 한 번씩 나타난다. 입력 줄의 정수들은 최소 한 개의 공백 문자로 구분된다. 입력의 끝은 두 개의 0이 있는 줄로 나타낸다.

각 지도에 대해 필요한 최소 미는 횟수를 한 줄에 출력한다. 화물을 목표 지점으로 옮길 수 없으면 대신 −1을 출력한다.