Informatica Online Judge

  구조요청 [2100 / 0834]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 22   Total Tried : 26


The Champion of this Problem (C++) : icp1481 - 4ms / 940byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs16059]

Background

GSHS의 유일한 등산 동아리, 광기에 속해있는 경곽이는 등산을 매우 좋아한다. 어느 날 경곽이는 로프를 가지고 N*M 크기의 광교산을 올라가다 길을 잃었다고 한다.

경곽이는 구조요청을 하기 위해 정해진 위치로 가야 한다. (등산은 4방향으로 움직인다.)

등산을 잘하는 경곽이는 자신이 있는 곳보다 낮은 지역은 얼마든지 갈 수 있지만 자신이 있는 곳보다 높은 곳은 로프를 써야지 갈 수 있다고 한다.

로프는 한번 쓰고 버린다고 할 때, 구조요청을 하기 위해 정해진 위치까지 가는데 소모되는 로프의 최솟값을 구하여라.

Input

첫 줄에는 산의 크기 N(1<=N<=1.000), M(1<=M<=500)이 주어진다. 둘째 줄부터 N*M 각각의 높이 H(1<=H<=1,000)가 주어진다.

경곽이의 처음 위치는 (1,1), 구조요청을 할 정해진 위치는 (N,M)이다.

Output

(N,M)까지 가는데 필요한 로프의 최솟값을 출력한다.

IO Example

입력
3 3
1 2 1
1 2 1
2 1 2

출력
2

입력
5 5
1 1 1 2 3
1 2 2 3 3
3 3 3 2 2
1 2 4 4 5
1 1 1 1 1

출력
1

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