페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4013

소는 왜 길을 건너갔을까? 7 2s 512MB

문제

소는 왜 길을 건너갔을까? 그 이유 중 하나는 그냥 길이 많아서이다.

존의 농장은 N^2개의 작은 정사각형 목초지가 N \times N 격자 정사각형 형태로 이루어져 있다.

기본적으로 소들은 인접한 목초지 사이를 자유롭게 동서남북으로 이동할 수 있고,
농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다.

소들은 다른 목초지로 이동하는 과정에서 길을 건너야 하는데, 길을 건너는데 T초가 소모되며, 길을 세 번 건널 때마다 풀을 한 번 먹어야 한다.
(이는 출발할 때는 해당되지 않지만, 도착할 때도 해당된다)

또한 목초지마다 풀이 자란 정도가 다를 수 있기에 풀 먹는 시간이 상이할 수 있다. (높이 1의 풀을 먹는데 1초가 걸린다)

소가 북서쪽 끝에 있는 목초지에서 남동쪽 끝에 있는 목초지까지 가는데 걸리는 최소 시간을 알아보자.


입력

첫 줄에 N과 T가 주어진다. (3 \leq N \leq 100, 0 \leq T \leq 1,000,000)

다음 N줄에 N개의 양의 정수 G_{i,j}가 주어져 각 목초지의 풀의 높이를 알려준다. (1 \le G_{i,j} \le 100\,000)

이 때, 가장 첫 줄의 처음 주어지는 목초지가 북서쪽이고, 가장 마지막 줄 마지막으로 주어지는 목초지가 남동쪽이다.


출력

소가 북서쪽 끝에 있는 목초지에서 남동쪽 끝에 있는 목초지까지 가는데 걸리는 최소 시간을 출력한다.


예제 

4 2
30 92 36 10
38 85 60 16
41 13 5 68
20 97 13 80
31

최적의 움직임은 동쪽으로 세 칸 이동하여 높이 10의 풀을 먹고, (2 \times 3 + 10 = 16)

남쪽으로 두 칸, 그리고 서쪽으로 한 칸 이동하여 높이 5의 풀을 먹은 뒤, (2 \times 3 + 5 = 11)

남쪽과 동쪽으로 한 칸씩 이동하여 남동쪽에 도착하는 것이다. (2 \times 2 = 4)

이러면 총 16 + 11 + 4 = 31초가 소모된다.



출처

USACO 2017 February Gold

로그인해야 코드를 작성할 수 있어요.