Check if possible to cross the matrix with given power | CPP program to find if it is possible to cross the matrix with given power ; Initializing array dp with false value . ; For each value of dp [ i ] [ j ] [ k ] ; For first cell and for each value of k ; For first cell of each row ; For first cell of each column ; For rest of the cell ; Down movement . ; Right movement . ; Diagonal movement . ; Finding maximum k . ; Driver Code
#include <bits/stdc++.h> NEW_LINE #define N  105 NEW_LINE #define R  3 NEW_LINE #define C  4 NEW_LINE using namespace std ; int maximumValue ( int n , int m , int p , int grid [ R ] [ C ] ) { bool dp [ N ] [ N ] [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { for ( int k = 0 ; k < N ; k ++ ) dp [ i ] [ j ] [ k ] = false ; } } for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { for ( int k = grid [ i ] [ j ] ; k <= p ; k ++ ) { if ( i == 0 && j == 0 ) { if ( k == grid [ i ] [ j ] ) dp [ i ] [ j ] [ k ] = true ; } else if ( i == 0 ) { dp [ i ] [ j ] [ k ] = ( dp [ i ] [ j ] [ k ] dp [ i ] [ j - 1 ] [ k - grid [ i ] [ j ] ] ) ; } else if ( j == 0 ) { dp [ i ] [ j ] [ k ] = ( dp [ i ] [ j ] [ k ] dp [ i - 1 ] [ j ] [ k - grid [ i ] [ j ] ] ) ; } else { dp [ i ] [ j ] [ k ] = ( dp [ i ] [ j ] [ k ] dp [ i ] [ j - 1 ] [ k - grid [ i ] [ j ] ] ) ; dp [ i ] [ j ] [ k ] = ( dp [ i ] [ j ] [ k ] dp [ i - 1 ] [ j ] [ k - grid [ i ] [ j ] ] ) ; dp [ i ] [ j ] [ k ] = ( dp [ i ] [ j ] [ k ] dp [ i - 1 ] [ j - 1 ] [ k - grid [ i ] [ j ] ] ) ; } } } } int ans = 0 ; for ( ans = k ; ans >= 0 ; ans -- ) if ( dp [ n - 1 ] [ m - 1 ] [ ans ] ) break ; return ans ; } int main ( ) { int n = 3 , m = 4 , p = 9 ; int grid [ R ] [ C ] = { { 2 , 3 , 4 , 1 } , { 6 , 5 , 5 , 3 } , { 5 , 2 , 3 , 4 } } ; cout << maximumValue ( n , m , p , grid ) << endl ; return 0 ; }