Maximum decimal value path in a binary matrix | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  4 NEW_LINE long long int MaximumDecimalValue ( int mat [ ] [ N ] , int n ) { int dp [ n ] [ n ] ; memset ( dp , 0 , sizeof ( dp ) ) ; if ( mat [ 0 ] [ 0 ] == 1 ) for ( int i = 1 ; i < n ; i ++ ) { if ( mat [ 0 ] [ i ] == 1 ) dp [ 0 ] [ i ] = dp [ 0 ] [ i - 1 ] + pow ( 2 , i ) ; else dp [ 0 ] [ i ] = dp [ 0 ] [ i - 1 ] ; } for ( int i = 1 ; i < n ; i ++ ) { if ( mat [ i ] [ 0 ] == 1 ) dp [ i ] [ 0 ] = dp [ i - 1 ] [ 0 ] + pow ( 2 , i ) ; else dp [ i ] [ 0 ] = dp [ i - 1 ] [ 0 ] ; } for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 1 ; j < n ; j ++ ) { if ( mat [ i ] [ j ] == 1 ) dp [ i ] [ j ] = max ( dp [ i ] [ j - 1 ] , dp [ i - 1 ] [ j ] ) + pow ( 2 , i + j ) ; else dp [ i ] [ j ] = max ( dp [ i ] [ j - 1 ] , dp [ i - 1 ] [ j ] ) ; } } return dp [ n - 1 ] [ n - 1 ] ; } int main ( ) { int mat [ ] [ 4 ] = { { 1 , 1 , 0 , 1 } , { 0 , 1 , 1 , 0 } , { 1 , 0 , 0 , 1 } , { 1 , 0 , 1 , 1 } , } ; cout << MaximumDecimalValue ( mat , 4 ) << endl ; return 0 ; }