Informatica Online Judge

  보물 [2259 / 08D3]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 0   Total Tried : 2


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[34th 박주원]
Writer ID : [gs16040]

Background

미지의 땅에 대한 지도를 얻은 경곽이는 보물을 찾으러 나선다.

미지의 땅은 거친 땅이기 때문에 한 칸을 이동할때마다 행동력을 소모한다.

경곽이는 일정한 행동력을 소모해 상하좌우 근접한 칸으로 이동할 수 있다.

이 때 소모하는 행동력은 도착하는 칸에 따라 결정되고, 소모하는 행동력은 무조건 1 이상이다.

다만 행동력이 1이라도 남아있으면 갖고 있는 행동력보다 많은 행동력이 필요한 칸에 행동력을 모두 소모하여 갈 수 있다.

가령 행동력이 2가 남아있고 행동력이 3이 필요한 칸이 바로 옆에 있다면 남은 행동력을 모두 소모해 그 칸으로 갈 수 있다.

경곽이는 하루에 k만큼의 행동력을 쓸 수 있고 지도의 크기는 n*n이라고 하자.

이제 경곽이가 보물이 있는 곳까지 며칠 걸리는지 구해보자.

Input

첫째 줄에는 지도의 크기 n(3≤n≤100)과 경곽이가 하루에 소모할 수 있는 행동력 k(1≤k≤10)이 주어진다..

두번째 줄과 세번째 줄에는 경곽이와 보물의 좌표가 주어진다. (경곽이와 보물의 좌표는 같지 않다.)

네번째 줄부터는 n*n 크기의 지도가 주어진다. 지도에는 그 칸으로 이동하는데 필요한 행동력이 주어진다.

Output

경곽이가 보물이 있는 곳까지 걸리는 일수를 출력한다.

IO Example

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

출력
3

*설명 : 첫째 날에 (1,3), 둘째 날에 (3,3), 셋째 날에 (4,4)로 가는 방법이 있다.

이 외에도 셋째 날에 도착할 수 있는 이동 경로는 많지만 둘째 날 이내에 도착할 수 있는 경우는 없다.

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