Informatica Online Judge

  오펜스 게임 1 [0987 / 03DB]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 49   Total Tried : 277


The Champion of this Problem (C++) : gs18105 - ms / 575byte
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

경곽이는 정보과학프로젝트 시간에 재미있는 오펜스 게임을 하나 만들었다.

오펜스 게임은 디펜스와 반대되는 개념이다. 최대한 $HP$를 덜 깍이면서 지정된 위치까지 탈출해야 하는 게임이다.

이 게임은 $N×N$행렬로 구성되어 있는 지도의 $1,1$에서 출발하여 $N,N$까지 이동해야한다.

이동 가능한 경로는 맵을 벗어나지만 않으면, 상, 하, 좌, 우 어디로든 이동 가능하다.

각 칸에는 플레이어가 받는 데미지가 적혀있다.

플레이어의 초기 체력과 각 맵의 데미지 정보가 주어질 때, 탈출 가능한지 판단하는 프로그램을 작성하시오.

만약 탈출이 불가능하다면 $-1$, 탈출이 가능하다면 남은 $HP$를 출력하시오.

Input

첫 번째 줄에 맵의 크기를 나타내는 정수 $N$과 플레이어의 체력 $H$가 공백으로 구분되어 입력된다.

두 번째 줄부터 $N$줄에 걸쳐서 각 줄에 $N$개 씩의 데미지를 나타내는 정수가 입력된다.

[입력값의 정의역]
$3 ≤ N ≤ 100$
$10 ≤ H ≤ 100,000$
$0 ≤ 데미지 ≤ 1,000$

[sub-task Info]
#1 : $3 ≤ n ≤ 10$
#2 : $10 {<} n ≤ 30$
#3, 4 : $30 {<} n ≤ 100$

Output

만약 탈출 가능하다면 남은 체력을 출력한다. 그렇지 않으면 $-1$을 출력한다.

IO Example

입력
3 10
1 2 3
1 2 3
1 1 2

출력
4

입력2
3 11
1 2 3
1 2 3
1 2 10

출력2
-1

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