Check if possible to cross the matrix with given power

Given a matrix of N X M, each cell consist of an integer. We have initial power of K and we are allowed to move right, down or diagonal. When we move to any cell, we absorb mat[i][j] value and lose that much amount from your power. If our power became less than 0 at any time, we cannot move further from that point. Now, our task is to find if there is any path from (1, 1) to (n, m) that we can cover with power k. If possible, output the maximum value we can absorb, else if there is no path print “-1”. 

Examples :

Input : N = 3, M = 3, K = 7
        mat[][] = { { 2, 3, 1 },
                    { 6, 1, 9 },
                    { 8, 2, 3 } };
Output : 6
Path (1, 1) -> (2, 2) -> (3, 3) to complete
journey to absorb 6 value.

Input : N = 3, M = 4, K = 9
        mat[][] = { 
                    { 2, 3, 4, 1 },
                    { 6, 5, 5, 3 },
                    { 5, 2, 3, 4 }
                  };
Output : -1

The idea is to use Dynamic Programming to solve the problem. Approach :

• Declare a boolean 3D matrix, say dp[ ][ ][ ], with N*M*(K+1) dimension such that dp[ i ][ j ][ k ] is true if it possible to reach the square in the i^th row and j^th column with exactly k value collected so far.
• We can write the recurrence dp[ i ][ j ][ k ] = true if either

dp[i-1][j][k-mat[i][j]] or 
dp[i][j-1][k-mat[i][j]] or 
dp[i-1][j-1][k-mat[i][j]] 

• i.e the three possible moves we could have.
• We have base case dp[0][0][0] be true.
• The answer is -2 if dp[n-1][m-1][k] is false for all k between 0 and k+1.
• Otherwise, the answer is the maximum k such that dp[n-1][m-1][k] is true.

Below is implementation of this approach : 

-1

Time Complexity: O(n³) 

If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.