119 구급대 > 문제은행



1113 : 119 구급대

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
568 회   
시도횟수
1561 회   

문제

철수네 동네의 소방서에서는 주민들의 편의를 위해 119 구급 대를 운영하고 있다. 가끔 일어나는 일이지만 위급한 일은 분초를 다투는 일이 많기 때문에 119 구급대가 위급한 일이 발생한 목표지점까지 최대한 빨리 도착해야 한다.

 

119 구급차는 성능이 좋아 일반 자동차보다 아주 빠른 속도로 주행할 수 있지만 코너를 돌 때에는 일반 자동차처럼 속도를 완전히 줄여야 하기 때문에 목표지점에 도달할 때 까지 되도록 코너를 돌지 않고 직선 도로를 통해 도착해야 시간을 줄일 수 있다.

 

e3050b66a1b29a01767400d7560a4131_1449730 

 

위의 테이블은 119 구급 대에서 위급한 일이 발생하는 목표지점까지의 지도를 표시한 것이다. 흰색으로 표시되어 있는 부분이 차가 지나갈 수 있는 길을 나타내고 회색으로 칠해져 있는 곳이 장애물을 의미한다. 이제 소방서에서 위급한 일이 발생한 목표지점까지 가장 빠른 시간에 도착할 수 있는 경로를 찾아보자. (출발점은 항상 왼쪽 맨 위(0,0)이고 도착점은 좌표로 주어진다. 119 구급차는 가로와 세로 방향으로만 움직일 수 있고 대각선으로는 움직일 수 없다.)


입력형식

첫째 줄에 지도의 크기 M(1≤M≤100)×N(1≤N≤100)이 주어진다. 두 번째 줄에는 목표점 m,n이 주어진다. (단 M=m+1, N=n+1) 다음 N줄에는 M개의 값이 주어지며 각 값에서 1은 도로이고 0은 진입할 수 없는 물건이 놓여 있다.


출력형식

첫째 줄에 최소 코너를 도는 횟수를 출력한다.


입력 예

10 10
9 7
1 1 1 0 1 1 0 1 1 1
1 1 1 0 0 1 1 1 0 0
1 0 1 0 1 1 0 1 1 1
1 1 1 1 1 0 0 0 0 1
0 1 0 0 1 1 1 1 0 1
1 1 1 1 1 0 0 1 1 1
1 0 0 1 0 0 1 1 0 1
1 0 1 1 1 1 1 0 0 0
1 1 0 1 1 0 1 1 0 1
0 1 1 1 0 1 1 1 1 1

출력 예

7


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP