Magic Grid

Moderate
0/80
3 upvotes
Asked in companies
HCL TechnologiesDunzoD.E.Shaw

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
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
Sample Output 1:
2
1
2
Hint

The very first approach can be to try all possible paths from top left to bottom right and minimize the health required.

Approaches (3)
Recursion

The main idea is to use recursion to reduce the big problem into several smaller subproblems.

 

  1. We will call a minimum_strength function that returns us the minimum health required from the current point to destination ('N' - 1, ‘M’ - 1).
  2. 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').
  3. 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.
Time Complexity

O(2 ^ (N + M)), Where ‘N’ is the number of rows and ‘M’ is the number of columns in the grid.

 

Since we are making 2 recursive calls for each cell visited with the maximum length covered will be (N + M). Thus the time complexity will be O(2 ^ (N + M)).

Space Complexity

O(N + M), Where ‘N’ is the number of rows and ‘M’ is the number of columns in the grid.

 

Since extra space is used by the recursion stack which goes to a maximum depth of N + M. Thus the space complexity will be O(N + M).

Code Solution
(100% EXP penalty)
Magic Grid
Full screen
Console