최단 거리 미로

프로그램 명: maze

제한시간: 1 초

도적들로부터 값진 보물을 훔쳐 달아나던 알리바바는 한 도시에 이르렀다. 그 도시는 전체가 마치 미로처럼 되어 있는 도시였는데 그 도시 한 쪽 끝에는 미리 준비해 놓은 배가 있어,도시 끝까지만 다다르면 도적들을 따돌릴 수 있다. 그런데 도적들은 이 도시에 대하여 잘아고 있기 때문에 도적들보다 먼저 출구에 다다르기 위해서는반드시 최단거리를 갖는 길로 가야만 한다.

도시의 지도가 주어질 때 최단 거리의 길을 찾는 프로그램을 작성하시오. 예를들어 도시의모양이 위와 같을 경우 입구에서 오른쪽으로 갈 경우 총 9 개의 블록(하얀 블록의 개수)를 지나 출구에 다다를 수 있다.

입력 형식

첫째 줄에 미로의 세로의 크기와 가로의 크기를 나타내는 자연수 N 과 M 이 이 주어지고 다음 N 줄에는 미로의 상태를 나타내는 M 개의 정수가 주어진다. 길은 0 으로 막힌 곳은 1 로 표시되며 모든 정보는 빈 칸 없이 붙어 있다. 입구는 항상 왼쪽 제일 아래 이고, 출구는 항상 오른쪽 제일 위이다. N 과 M 은 20 이하의 자연수이다.

출력 형식

첫 줄에 최단 거리의 길로 갈 경우 거쳐야 하는 블록의 개수를 출력한다. 만약 출구에 이르는 길이 없다면 -1 을 출력한다.

입출력 예

[질/답] [제출 현황] [푼 후(2)]

[ 채 점 ] [홈으로] [뒤 로]