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

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

위의 테이블은 119 구급 대에서 위급한 일이 발생하는 목표지점까지의 지도를 표시한 것이다.

흰색으로 표시되어 있는 부분이 차가 지나갈 수 있는 길을 나타내고 회색으로 칠해져 있는 곳이 장애물을 의미한다.

이제 소방서에서 위급한 일이 발생한 목표지점까지 가장 빠른 시간에 도착할 수 있는 경로를 찾아보자. (출발점은 항상 왼쪽 맨 위(0,0)이고 도착점은 좌표로 주어진다. 119 구급차는 가로와 세로 방향으로만 움직일 수 있고 대각선으로는 움직일 수 없다.)

119 구급대 timer 1s memory 64MB

119 구급대 1s 64MB