Maximum decimal value path in a binary matrix | Python3 program to find Maximum decimal value Path in Binary matrix ; Returns maximum decimal value in binary matrix . Here p indicate power of 2 ; Compute binary stream of first row of matrix and store result in dp [ 0 ] [ i ] ; indicate 1 * ( 2 ^ i ) + result of previous ; indicate 0 * ( 2 ^ i ) + result of previous ; Compute binary stream of first column of matrix and store result in dp [ i ] [ 0 ] ; indicate 1 * ( 2 ^ i ) + result of previous ; indicate 0 * ( 2 ^ i ) + result of previous ; Traversal rest Binary matrix and Compute maximum decimal value ; Here ( i + j ) indicate the current power of 2 in path that is 2 ^ ( i + j ) ; Return maximum decimal value in binary matrix ; Driver program
N = 4 NEW_LINE def MaximumDecimalValue ( mat , n ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( n ) ] for i in range ( n ) ] NEW_LINE if ( mat [ 0 ] [ 0 ] == 1 ) : NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if ( mat [ 0 ] [ i ] == 1 ) : NEW_LINE INDENT dp [ 0 ] [ i ] = dp [ 0 ] [ i - 1 ] + 2 ** i NEW_LINE DEDENT else : NEW_LINE INDENT dp [ 0 ] [ i ] = dp [ 0 ] [ i - 1 ] NEW_LINE DEDENT DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT if ( mat [ i ] [ 0 ] == 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = dp [ i - 1 ] [ 0 ] + 2 ** i NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT dp [ i ] [ 0 ] = dp [ i - 1 ] [ 0 ] NEW_LINE DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( 1 , n ) : NEW_LINE INDENT if ( mat [ i ] [ j ] == 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = max ( dp [ i ] [ j - 1 ] , dp [ i - 1 ] [ j ] ) + ( 2 ** ( i + j ) ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = max ( dp [ i ] [ j - 1 ] , dp [ i - 1 ] [ j ] ) NEW_LINE DEDENT DEDENT DEDENT return dp [ n - 1 ] [ n - 1 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mat = [ [ 1 , 1 , 0 , 1 ] , [ 0 , 1 , 1 , 0 ] , [ 1 , 0 , 0 , 1 ] , [ 1 , 0 , 1 , 1 ] ] NEW_LINE print ( MaximumDecimalValue ( mat , 4 ) ) NEW_LINE DEDENT