Informatica Online Judge

  필사의 탈출 1 [0890 / 037A]

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


The Champion of this Problem (C++) : newton - 6ms / 867byte
My Best Submission (C++) : N/A

[JKJeong 2013]

Background

경곽이의 연구실에 불이나서 재빨리 탈출을 해야한다.

경곽이의 연구실 건물은 N*N의 격자형으로 구성되어 있다.

경곽이의 연구실은 (1,1), 출구는 (N,N)에 위치한다.

가스 탐지기로 검사한 결과 각 칸의 유독가스량이 주어진다. 경곽이는 최대한 짧은 거리로 탈출하기 위하여 최단 경로로만 움직이기로 했다. 즉, 아래 혹은 오른쪽으로만 이동한다.

가스의 피해를 최소화하여 탈출할 수 있도록 경곽이를 도와주자.

Input

첫 번째 줄에 방의 크기 N이 주어진다.
두 번째 줄부터 N줄에 걸쳐서 N개의 정수 G_ij가 공백으로 구분되어 입력된다.
G_ij는 (i, j)의 유독가스의 양이다.

[입력값의 정의역]
3 <= N <= 1,000
-10 <= G_ij <= 1,000 (1 <= i, j <= N )

Output

가스의 최소 피해치를 출력한다.

IO Example

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

출력
3

[설명]
(1,1) - (2,1) - (3,1) - (3,2) - (3,3) 으로 이동할 경우 0 + 1 + 0 + 1 + 1 = 3으로 3의 피해로 탈출할 수 있다. 물론 3으로 탈출할 수 있는 다른 경로도 있지만 3이하로 탈출할 수 있는 방법은 없다.

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