Informatica Online Judge

  젖소 심마니 [0219 / 00DB]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 162   Total Tried : 206


The Champion of this Problem (C++) : gs17067 - ms / 854byte
My Best Submission (C++) : N/A

[]

Background

농부 존은 최근 산삼의 효능에 흥미를 가지고 산삼을 캘 수 있는 소를 길러내었다.

이 심마니 소는 험한 산속에서 산삼의 위치를 알아내는 독특한 능력을 가지게 되었다. 베시가 몸이 좋지 않아 지금 당장 산삼이 필요한 입장이 되었다.

농부 존은 베시를 아주 아끼기 때문에 그의 빠른 치료를 위하여 급히 산삼이 필요하게 되었다. 따라서 심마니 소에게 무전으로 산삼 하나를 구해오라고 연락을 했다. 심마니 소는 현재 자기가 있는 지역에서 존재하는 여러 개의 산삼 중에 하나의 산삼을 캐서 농부 존에게로 가장 빠르게 갈 수 있도록 농부 존을 도와주자.

심마니 소는 현재 지역의 지도를 가지고 있다.

이 지도는 H행 W열( 1 <= W, H <= 1000 )의 사각형 격자형으로 구성되어 있으며 이동 가능한 길은 동, 서, 남, 북 사방으로만 이동 가능하며, 한 영역을 이동하는데 1일이 소요된다. (대각선으로는 이동 불가) 이 지도를 이용하여 위의 문제를 해결할 수 있는 프로그램을 작성하시오.

Input

첫째 줄에는 2개의 공백으로 구분된 정수 W, H가 차례로 입력된다. 각 지도의 영역별 값이 입력되는데 각 영역별 값은 다음과 같은 의미를 지닌다.

* 0 : 심마니 소가 이동 할 수 있는 영역
* 1 : 심마니 소가 이동할 수 없는 영역 (절벽, 폭포 등의 영역)
* 2 : 심마니 소의 출발 지점
* 3 : 현재 농부 존이 있는 위치
* 4 : 산삼의 위치 (여러 개 있을 수 있음)

Output

심마니 소가 산삼을 하나 구하여 농부 존에게로 가는 최소의 일수를 구하여 하나의 정수로 출력한다.

IO Example

입력
8 4
4 1 0 0 0 0 1 0
0 0 0 1 0 1 0 0
0 2 1 1 3 0 4 0
0 0 0 4 1 1 1 0

출력
11

설명>
위의 경우 심미나 소가 다음과 같은 경로로 이동하는 것이 최고 빠르게 구해서 갈 수 있는 경우이다.
상-좌-상-하-우-우-상-우-우-하-하 (11일)


출처 : USACO (http://ace.delos.com)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]