시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 45 15 9 25.714%

문제

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

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

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

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

입력

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

출력

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

예제 입력

10 10
0000000000
0200000000
0000000000
0100000000
0000000000
0111111130
0000000000
0000000000
0000000000
0000000000

예제 출력

5

힌트