생산 라인의 점검 운반차

문제

한 공장은 생산 라인 사이에 작은 점검 운반차가 다닐 수 있는 통로를 마련했다. 공장 바닥은 H행 W열의 직사각형 칸으로 나뉘어 있으며, 각 칸에는 설비가 놓여 있거나 운반차가 지나갈 수 있는 통로가 있다. 운반차는 출발 대기 칸에서 점검 부품을 싣고 출발하여, 부품을 기다리는 도착 칸까지 이동해야 한다. 바닥 지도는 숫자 문자 네 종류로 주어진다. 0은 설비가 차지한 칸, 1은 일반 통로, 2는 출발 대기 칸, 3은 도착 칸을 뜻한다. 지도에는 2와 3이 각각 정확히 하나씩 있다. 출발 칸과 도착 칸도 운반차가 지나갈 수 있는 칸이다. 설비가 차지한 칸에는 어떤 경우에도 들어갈 수 없으며, 운반차가 이동하는 동안 지도는 변하지 않는다. 운반차는 현재 칸에서 위, 아래, 왼쪽, 오른쪽으로 변을 맞댄 칸 중 하나로 이동할 수 있다. 대각선으로 이동하거나 지도 밖으로 나가는 일은 허용되지 않는다. 이동 가능한 이웃 칸으로 한 번 이동할 때마다 정확히 1초가 걸린다. 방향을 바꾸는 데에는 별도의 시간이 들지 않으며, 같은 칸을 여러 번 방문하는 것도 허용된다. 부품을 싣거나 내려놓는 시간은 계산하지 않는다. 운영자는 운반차를 출발시키기 전에 가장 빠른 도착 시간을 알고자 한다. 출발 칸에서 도착 칸까지 도달하는 데 필요한 최소 이동 시간을 구한다. 통로가 여러 갈래로 나뉘거나 다시 합쳐질 수 있으므로, 지도에서 보이는 한 방향으로만 계속 이동할 필요는 없다. 도착할 수 있는 경로가 여러 개이면 그중 이동 횟수가 가장 작은 경로의 시간만 출력한다. 경로 자체나 경로의 개수는 출력하지 않는다. 설비 때문에 출발 칸과 도착 칸이 완전히 분리되어 있다면 도착할 수 없음을 나타내는 -1을 출력한다.

입력

첫째 줄에 정수 H와 W가 공백으로 주어진다. 1 ≤ H, W ≤ 1,000이며 2 ≤ H × W ≤ 200,000이다.
다음 H개 줄에 각 행의 지도가 주어진다. 각 줄은 공백 없이 정확히 W개의 문자로 이루어지며, 각 문자는 0, 1, 2, 3 중 하나이다. 전체 지도에서 2와 3은 각각 정확히 한 번 등장한다.

출력

출발 칸에서 도착 칸까지의 최소 이동 시간을 초 단위의 정수로 한 줄에 출력한다. 도착할 수 없으면 -1을 출력한다.

3 4
2110
0010
0113

5

2 3
201
013

-1

1 2
23

1

출처: Devin.KR 자체 제작