AMR11A - Magic Grid

no tags 

Thanks a lot for helping Harry Potter in finding the Sorcerer's Stone of Immortality in October. Did we not tell you that it was just an online game? uhhh! Now here is the real onsite task for Harry. You are given a magrid S (a magic grid) having R rows and C columns. Each cell in this magrid has either a Hungarian horntail dragon that our intrepid hero has to defeat, or a flask of magic potion that his teacher Snape has left for him. A dragon at a cell (i, j) takes away |S[i][j]| strength points from him, and a potion at a cell (i, j) increases Harry's strength by S[i][j]. If his strength drops to 0 or less at any point during his journey, Harry dies, and no magical stone can revive him.

Harry starts from the top-left corner cell (1, 1) and the Sorcerer's Stone is in the bottom-right corner cell (R, C). From a cell (i, j), Harry can only move either one cell down or right i.e., to cell (i+1, j) or cell (i, j+1) and he can not move outside the magrid. Harry has used magic before starting his journey to determine which cell contains what, but lacks the basic simple mathematical skill to determine what minimum strength he needs to start with to collect the Sorcerer's Stone. Please help him once again.

Input

The first line contains the number of test cases T. T cases follow. Each test case consists of R C in the first line followed by the description of the grid in R lines, each containing C integers. Rows are numbered 1 to R from top to bottom and columns are numbered 1 to C from left to right. Cells with S[i][j] < 0 contain dragons, others contain magic potions.

Output

Output T lines, one for each case containing the minimum strength Harry should start with from the cell (1, 1) to have a positive strength through out his journey to the cell (R, C).

Constraints

1 ≤ T ≤ 5

2 ≤ R, C ≤ 500

-10^3 ≤ S[i][j] ≤ 10^3

S[1][1] = S[R][C] = 0

Sample

Input:
3
2 3
0 1 -3
1 -2 0
2 2
0 1
2 0
3 4
0 -2 -3 1
-1 4 0 -2
1 -2 -3 0

Output:
2
1
2

Explanation:

Case 1: If Harry starts with strength = 1 at cell (1, 1), he cannot maintain a positive strength in any possible path. He needs at least strength = 2 initially.

Case 2: Note that to start from (1, 1) he needs at least strength = 1.


hide comments
Sushovan Sen: 2022-02-01 13:21:51

@vidz_1
Consider Case:
2 3
0 -5 2
2 -5 24
3 -1 0
Check whether your approach gives correct result.

vidz_1: 2020-09-24 14:46:48

Why can't we just do normal forward dp and make the table. Later we go from last block to initial block always going to the best path(max(dp[i-1][j],dp[i][j-1]) because that's how the table would be built, find the min value and return mod(min)+1 as the answer ? Can someone please help, I am getting a WA.

tokyoghoul1993: 2019-12-29 10:12:16

Can someone plz explain how binary search is used here?
I have been able to solve using backward dp but still can't see how to do same using binary search..

yashranjan74: 2019-09-17 22:44:03

Nice problem. Can be easily done with any way, Top-Down DP or Bottom-Up DP.

chirayu_555: 2019-08-14 21:03:12

AC in one go..!! Nice problem..!!

geekymanas_: 2019-07-29 14:17:17

There are two ways to do this. First is moving forward dp with Binary Search, second moving backward just dp

Last edit: 2019-07-29 18:57:29
Asokan R: 2019-01-04 21:47:39

Bottom up DP in Java gives TLE, but same code in c++ is accepted

Last edit: 2019-01-04 21:47:55
hello_world123: 2018-07-14 21:50:06

Keep in mind that initial strength is minimum 1.

shahi9935: 2018-06-26 05:28:32

Thanks @sherlock11

Last edit: 2018-06-26 05:29:02
sherlock11: 2018-06-23 15:02:31

its not much of dp problem rather a variation of binary search...................


Added by:Varun Jalan
Date:2011-12-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Anil Kishore - ICPC Asia regionals, Amritapuri 2011