Last Updated: 11 Oct, 2017
Magic Grid
Moderate
Asked in companies
You are given a magic grid A with R rows and C columns. In the cells of the grid, you will either get magic juice, which increases your strength by |A[i][j]| points, or poison, which takes away |A[i][j]| strength points. If at any point of the journey, the strength points become less than or equal to zero, then you will die.
You have to start from the top-left corner cell (1,1) and reach at the bottom-right corner cell (R,C). From a cell (i,j), you can only move either one cell down or right i.e., to cell (i+1,j) or cell (i,j+1) and you can not move outside the magic grid. You have to find the minimum number of strength points with which you will be able to reach the destination cell.
Input format:
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 A[i][j] < 0 contain poison, others contain magic juice.
Output format:
Output T lines, one for each case containing the minimum strength you 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 ≤ A[i][j] ≤ 10^3
A[1][1] = A[R][C] = 0
Time Limit: 1 second
Approaches
The main idea is to use recursion to reduce the big problem into several smaller subproblems.
- We will call a minimum_strength function that returns us the minimum health required from the current point to destination ('N' - 1, ‘M’ - 1).
- From each point ('i' , ‘j’), we have 2 choices:
- We can move right to ('i' , ‘j’ + 1). Then we will do a recursive call with ('i' , ‘j’ + 1) as our starting point, say the minimum health required from this call comes out to be ‘A’.
- Or we can move down to ('i' + 1 , ‘j’). Then we will do a recursive call with ('i' + 1, ‘j’) as our starting point, say the minimum health required from this call comes out to be ‘B’.
- Then our minimum health required from ('i' , ‘j’) to ('N' - 1,'M' - 1) will be 'grid[i][j]' + min('A','B').
- The algorithm for minimum_strength will be as follows:
- Int minimum_strength('grid', ‘i’, ‘j’, ‘N’, 'M)
- If ‘i’ >= ‘N’ or ‘j’ >= ‘M’ : if the point is out of grid.
- return INT_MAX
- If ‘i’ == ‘N’ - 1 and j == ‘M’ - 1:
- if 'grid[i][j]' ≤ 0:
- return abs(grid[i][j] + 1
- else:
- return 1
- Int ‘A’ = minimum_strength ('grid', 'i', 'j' + 1, ‘N’, ‘M’)
- Int 'B' = minimum_strength ('grid', ‘i’ + 1, ‘j’, ‘N’, ‘M’)
- if minHealthRequired ≤ 0:
- return 1
- else
- return minHealthRequired.
- Int minimum_strength('grid', ‘i’, ‘j’, ‘N’, 'M)
We can see that we were solving the same subproblems multiple times. Thus, this problem was exhibiting overlapping subproblems. This means, in this approach, we need to eliminate the need for solving the same subproblems again and again. Thus, the idea is to use Memoization.
The steps are as follows:
- Create a ‘dp’ table of size ‘N’ * ‘M’ to store the answers to the subproblems where ‘lookUp[i][j]’ denotes minimum health required from ('i', 'j') to ('N' - 1, 'M' - 1)
- Initialize the ‘dp’ array with -1 which denotes that it is not calculated yet.
- We will call a minimum_strength function that returns us the minimum path sum.
- The algorithm for minimum_strength will be as follows:
- Int minimum_strength('grid', ‘i’, ‘j’, ‘N', ‘M’)
- If 'i' >= ‘N’ or ‘j’ >= 'M' : if the point is out of grid.
- return a large integer value
- If ‘i’ == ‘N’ - 1 and ‘j’ == ‘M’ - 1:
- if 'grid[i][j]' ≤ 0:
- return abs(grid[i][j] + 1
- else:
- return 1
- If ‘dp[i][j]’ != -1: means we have already calculated the answer for this sub-problem,
- return ‘dp[i][j]’.
- Int ‘A’ = minimum_strength('grid', ‘i’, ‘j’ + 1, ‘N’, 'M')
- Int ‘B’ = minimum_strength('grid', 'i' + 1, 'j', ‘N’, ‘M’)
- ‘minHealthRequired’ = -grid[i][j] + min('A', ‘B’).
- if minHealthRequired ≤ 0:
- dp[i][j] = 1
- else
- dp[i][j] = minHealthRequired
- Return 'dp[i][j]'.
- Int minimum_strength('grid', ‘i’, ‘j’, ‘N', ‘M’)
Initially, we were breaking the large problem into small problems but now, let us look at it differently. The idea is to solve the small problem first and then reach the final answer. Thus we will be using a bottom-up approach now.
We are using the value of dp[i][j] for calculating the dp values. We will use our dp array as our dp table.
The steps are as follows:
- For i = 0 to i ≤ N:
- For j = 0 to j ≤ M:
- Initialize dp[i][j] as a large integer value.
- For ‘i’- ‘N’ - 1 to 0:
- For ‘j’- ‘M’ - 1 to 0:
- ‘neededStrength’ = min ( ‘dp[i+1][j]’ , ‘dp[i][j+1]’) - ‘grid[i][j]’.
- If neededStrength ≤ 0
- dp[i][j] = 1
- else:
- dp[i][j] = neededStrength
- If neededStrength ≤ 0
- ‘neededStrength’ = min ( ‘dp[i+1][j]’ , ‘dp[i][j+1]’) - ‘grid[i][j]’.
- Finally, return 'dp[0][0]'.