10048 미로 탐색 Silver I

문제

N×M 크기의 미로가 주어진다. 미로에서 1은 이동할 수 있는 칸이고, 0은 이동할 수 없는 칸이다. (1, 1)에서 (N, M)까지 이동할 때 지나야 하는 최소 칸 수를 구하는 프로그램을 작성하시오. 시작 칸과 도착 칸도 포함한다.

이동은 상하좌우 인접한 칸으로만 가능하다.

입력

첫째 줄에 N (2 ≤ N ≤ 100)과 M (2 ≤ M ≤ 100)이 주어진다. 다음 N개의 줄에 미로가 주어진다. 시작 칸과 도착 칸은 항상 1이다.

출력

(1, 1)에서 (N, M)까지 지나야 하는 최소 칸 수를 출력한다. 도달할 수 없는 경우 -1을 출력한다.

4 6
101111
101010
101011
111011

15