RiseOJ – 소는 왜 길을 건넜을까

설명

소는 왜 길을 건넜을까? 한 가지 이유는 농부 존의 농장에 도로가 워낙 많아서, 소들이 여러 도로를 건너지 않고는 돌아다닐 수 없기 때문이다.

FJ의 농장은 $N \times N$ 정사각형 격자 모양의 들판들로 이루어져 있으며 ( $3 \leq N \leq 100$ ), 농장 내부를 지나는 $$N-1$$ 개의 남북 방향 도로와 $$N-1$$ 개의 동서 방향 도로가 들판들 사이의 경계 역할을 한다. 바깥 둘레에는 높은 울타리가 둘러쳐져 있어 소들이 농장을 떠날 수 없다. 소 베시는 두 들판을 가르는 도로를 건너기 전에 양쪽을 잘 살피기만 하면, 어떤 들판에서든 인접한(북, 동, 남, 서) 들판으로 자유롭게 이동할 수 있다. 베시가 도로 하나를 건너는 데는 $$T$$ 단위의 시간이 걸린다 ( $0 \leq T \leq 1,000,000$ ).

어느 날 FJ는 베시를 자신의 집으로 초대해 친선 체스 게임을 하자고 한다. 베시는 북서쪽 모서리 들판에서 출발하고 FJ의 집은 남동쪽 모서리 들판에 있으므로, 베시는 꽤 먼 길을 걸어야 한다. 베시는 가는 길에 배가 고파지기 때문에, 방문하는 들판 세 곳마다 한 번씩 멈춰서 풀을 뜯는다(출발 들판은 포함하지 않지만, FJ의 집이 있는 마지막 들판은 포함될 수 있다). 어떤 들판은 다른 들판보다 풀이 무성하므로, 풀을 뜯기 위해 멈추는 데 필요한 시간은 멈추는 들판에 따라 다르다.

베시가 FJ의 집에 도착하는 데 걸리는 최소 시간을 구하도록 도와주자.

문제 출처: Brian Dean

제약

문제 출처: Brian Dean

입력 형식

입력의 첫째 줄에 $$N$$ 과 $$T$$ 가 주어진다. 다음 $$N$$ 개의 줄에는 각 들판에서 풀을 뜯는 데 필요한 시간을 나타내는 $$N$$ 개의 양의 정수(각각 100,000 이하)가 주어진다. 첫째 줄의 첫 번째 수가 북서쪽 모서리이다.

출력 형식

베시가 FJ의 집까지 이동하는 데 필요한 최소 시간을 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 visitfj.in · 출력을 쓸 파일 visitfj.out

예제 1

입력

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

출력

설명

The optimal solution for this example involves moving east 3 squares (eating the
"10"), then moving south twice and west once (eating the "5"), and finally
moving south and east to the goal.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > February > Gold

올림피아드 > USACO > 2016-2017 > February > Gold

태그

JudgeUSACO

소는 왜 길을 건넜을까

평가 및 의견

풀이 제출