미로 생성기

마법사가 N×M 격자로 이루어진 미로를 생성했다. 미로의 각 칸은 길(0) 또는 벽(1)이다. 입구(0,0)에서 출구(N-1,M-1)까지 이동하는 최소 칸 수를 구하여라. 이동은 상하좌우로만 가능하다.

입력

첫째 줄에 행 수 N과 열 수 M이 주어진다. 다음 N줄에 걸쳐 미로 상태가 0과 1의 문자열로 주어진다.

출력

최소 이동 칸 수를 출력한다. 도달 불가능하면 -1을 출력한다.

제한

• 2 ≤ N, M ≤ 1000
• 시작과 끝 칸은 항상 길(0)이다

예제 입력 1

4 4
0010
1000
1101
0000

예제 출력 1

6

예제 입력 2

3 3
000
110
110

예제 출력 2

4

설명: 예제 1에서 (0,0)→(0,1)→(1,1)→(1,2)→(1,3)→(2,3)→(3,3) 경로로 6칸 이동. 예제 2에서 (0,0)을 포함해 4칸이 최단이다.