The Rock Jungle
All submissions for this problem are available.
John is trapped in a jungle of rocks, which can be represented as a square matrix J of size [1..N][1..N]. He has the map of this jungle. He is currently stuck at the position J[1,1]. He desires to go the exit of the jungle, where he can find the river and save himself. This exit is at position J[N,N]. He can move one step in any three of the given directions from his current position: East, South or South-East. Each position, other than J[1,1] has a rock in it, as mentioned. John requires some energy to break a rock and continue his journey. The energy required to break a rock at position J[i,j] is given by a positive integer at J[i,j]. John has E amount of energy at the moment, i.e, at J[1,1]. John wants to have maximum energy on reaching the exit, hence he chooses the best path to the exit. Find out how much energy he will have remaining at the exit. It is guaranteed that John will have enough energy to reach the exit.
Note: This problem is inspired from this problem on CodeChef
The first line of the input contains an integer T denoting the number of test cases. Then the description of each of the T cases are as follows:
The first line of a test case has two space separated integers N and E, the size of the jungle matrix and the energy that John has at J[1,1] respectively. Then, there are N lines describing the contents of the matrix J.
For each test case, print the amount of energy John has left at the exit
- 1 <= T <= 5
- 2 <= N <= 100
- 1 <= E <= 10^5
- 1 <= J[i,j] <= 500
- J[1,1] = 0, always
Input: 1 3 50 0 2 3 4 2 1 1 1 1 Output: 47
If John moves across the diagonal, he will spend only 3 (2 + 1) amount of energy, and have 47 (50 - 3) left
|Time Limit:||0.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.