14947번 - 상자 배달

택배 배달원인 박건은 택배를 손님 집으로 옮겨야 한다. 돈이 없는 박건은 직접 상자를 굴려서 옮기기로 했다.

상자는 1×1×3모양이고 처음에는 1×1이 밑면인 상태다.

최근 싱크홀이 많이 일어나서 땅에 구멍이 나있다. 상자를 구멍에 빠트리면 목표지점까지 옮길 수 없다. 1×3이 밑면일 때는 세 면 중 양 옆 모두 땅이 있거나 가운데에 땅이 있을 때에만 버틸 수 있다. 그 외의 경우에는 상자가 떨어져서 운반할 수가 없다.

지도와 시작 위치, 도착지점이 주어져 있으면 상자를 최소 몇번 굴려서  목표지점까지 도달할 수 있는지 구하여라. 도착지점에서 상자가 꼭 서있을 필요는 없다. 어떤 면이든 도착지점에 닿기만 하면 된다. 하지만 상자가 굴러 떨어지면 안 된다. 박스는 밖으로 벗어나면 안 된다. 상자를 굴릴 때는 항상 어떤 변이 바닥과 붙어있어야 한다.

처음 지도의 세로 크기 n과 가로 크기 m이 주어진다(1 ≤ n ≤ 500, 1 ≤ m ≤ 500). 다음 n개의 줄에는 m개의 숫자가 주어진다. 0은 싱크홀이고 1은 땅, 2는 시작지점, 3은 목적지다.

목표지점까지 최소 몇번 옮길 수 있는지 출력해라. 만약 옮길 수 없으면 -2를 출력해라.