Check if possible to cross the matrix with given power | Python3 program to find if it is possible to cross the matrix with given power ; 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
N = 105 NEW_LINE R = 3 NEW_LINE C = 4 NEW_LINE def maximumValue ( n , m , p , grid ) : NEW_LINE INDENT dp = [ [ [ False for i in range ( N ) ] for j in range ( N ) ] for k in range ( N ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( m ) : NEW_LINE INDENT k = grid [ i ] [ j ] NEW_LINE while ( k <= p ) : NEW_LINE INDENT if ( i == 0 and j == 0 ) : NEW_LINE INDENT if ( k == grid [ i ] [ j ] ) : NEW_LINE INDENT dp [ i ] [ j ] [ k ] = True NEW_LINE DEDENT DEDENT elif ( i == 0 ) : NEW_LINE INDENT dp [ i ] [ j ] [ k ] = ( dp [ i ] [ j ] [ k ] or dp [ i ] [ j - 1 ] [ k - grid [ i ] [ j ] ] ) NEW_LINE DEDENT elif ( j == 0 ) : NEW_LINE INDENT dp [ i ] [ j ] [ k ] = ( dp [ i ] [ j ] [ k ] or dp [ i - 1 ] [ j ] [ k - grid [ i ] [ j ] ] ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] [ k ] = ( dp [ i ] [ j ] [ k ] or dp [ i ] [ j - 1 ] [ k - grid [ i ] [ j ] ] ) NEW_LINE dp [ i ] [ j ] [ k ] = ( dp [ i ] [ j ] [ k ] or dp [ i - 1 ] [ j ] [ k - grid [ i ] [ j ] ] ) NEW_LINE dp [ i ] [ j ] [ k ] = ( dp [ i ] [ j ] [ k ] or dp [ i - 1 ] [ j - 1 ] [ k - grid [ i ] [ j ] ] ) NEW_LINE DEDENT k += 1 NEW_LINE DEDENT DEDENT DEDENT ans = k NEW_LINE while ( ans >= 0 ) : NEW_LINE INDENT if ( dp [ n - 1 ] [ m - 1 ] [ ans ] ) : NEW_LINE INDENT break NEW_LINE DEDENT ans -= 1 NEW_LINE DEDENT return ans NEW_LINE DEDENT n = 3 NEW_LINE m = 4 NEW_LINE p = 9 NEW_LINE grid = [ [ 2 , 3 , 4 , 1 ] , [ 6 , 5 , 5 , 3 ] , [ 5 , 2 , 3 , 4 ] ] NEW_LINE print ( maximumValue ( n , m , p , grid ) ) NEW_LINE