Informatica Online Judge

  Interstella [1176 / 0498]

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


The Champion of this Problem (C++) : gs15120 - 0ms / 1763byte
My Best Submission (C++) : N/A

[koistudy.net (31st 석연욱)]

Background

평소에 영화를 좋아하는 민규는 2014년 최고로 "핫"한 영화인 인터스텔라(Interstella,2014)를 보고 싶어한다. 하지만 영화표 구하기가 하늘에 별 따기보다 어려운 나머지 기다리고만 있는데......

그러나 경기과학고등학교에는 이미 인터스텔라를 관람한 친구들이 많았다. 그들은 민규의 사기를 떨어뜨리기 위해 민규를 만날 때마다 스포를 한다.

여기저기서 봇물처럼 터지는 스포를 듣다가 영화가 재미없을 것 같은 민규는 빨리 학교를 탈출하여 영화관으로 가고자 하는데...

안타깝게도 민규가 영화관으로 가는 곳곳에 많은 친구들이 기다리고 있다.
민규를 도와 민규가 가장 행복하게 만들어 주자.

민규가 있는 학교는 N*N의 공간이고 현재 민규의 위치는 (0,0), 영화관의 위치는 (N-1,N-1)이다.

학교는 각 위치마다 높낮이가 다른데, 낮은 곳에서 높은 곳으로는 이동할 수 없고, 민규는 항상 최단거리로만 이동한다.

그리고 각 위치에는 친구들이 민규를 기다리고 있는데 친구들마다 스포를 하는 정도가 다르다.

민규가 가장 적은 양의 스포를 듣게하는 경로를 찾아주자.

Input

입력 파일의 첫째 줄에는 학교의 크기를 나타내는 정수 N이 공백을 두고 입력된다.

두번째 줄에서 (N+1)줄까지 한 줄에 N개씩 공백을 두고 각 위치의 높이를 나타내는 정수들 h_ij가 입력된다.

(N+2)줄에서 (2N+1)줄까지 한 줄에 N개씩 공백을 두고 각 위치에서 친구들의 스포 정도를 나타내는 정수들 s_ij가 입력된다.

[입력값의 정의역]
0 <= N <= 210
-1 <= h_ij <=2
0 <= s_ij <= 99

Output

민규가 들을 수 있는 최소의 스포 정도의 수치를 출력한다.
만약 민규가 영화관을 갈 수 없다면 -1을 출력한다.

IO Example

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

출력 1
6

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

출력 2
-1

*출력 2 설명 : 영화관에 갈 수 없으므로 -1을 출력한다.

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