Tutorialspoint.dev

Maximum decimal value path in a binary matrix

Given binary square matrix [n*n]. Find maximum integer value in a path from top left to bottom right. We compute integer value using bits of traversed path. We start at index [0,0] and end at index [n-1][n-1]. from index [i, j], we can move [i, j+1] or [i+1, j].

Examples:

Input : mat[][] = {{1, 1, 0, 1},
                   {0, 1, 1, 0},
                   {1, 0, 0, 1},
                   {1, 0, 1, 1}}
Output : 111
Explanation : 
Path :   (0,0) -> (0,1) -> (1,1) -> (1,2) ->
         (2,2) -> (3,2) ->(4,4)  
Decimal value : 1*(2^0) + 1*(2^1) + 1*(2^2) + 1*(2^3) + 
                0*(2^4) + 1*(2^5) + 1*(2^6) = 111



The above problem can be recursively defined as below:

// p indicates power of 2, initially  p = i = j = 0
MaxDecimalValue(mat, i, j, p) 

   // If i or j is our of boundary
   If i >= n || j >= n  
      return 0

   // Compute rest of matrix find maximum decimal value 
   result  max(MaxDecimalValue(mat, i, j+1, p+1), 
               MaxDecimalValue(mat, i+1, j, p+1))

   If mat[i][j] == 1  
      return power(2, p) + result
   Else
      return result 

Below is the implementation of above recursive algorithm.

C++

    
// C++ program to find maximum decimal value path in
// binary matrix
#include<bits/stdc++.h>
using namespace std;
  
#define N 4
  
// Returns maximum decimal value in binary matrix.
// Here p indicate power of 2
long long int maxDecimalValue(int mat[][N], int i, int j,
                                                   int p)
{
    // Out of matrix boundary
    if (i >= N || j >= N )
        return 0;
  
    int result = max(maxDecimalValue(mat, i, j+1, p+1),
                     maxDecimalValue(mat, i+1, j, p+1));
  
    // If current matrix value is 1 then return result +
    // power(2, p) else result
    if (mat[i][j] == 1)
        return pow(2, p) + result;
    else
        return result;
}
  
//Driver program
int main()
{
    int mat[][4] = {{ 1 ,1 ,0 ,1 },
        { 0 ,1 ,1 ,0 },
        { 1 ,0 ,0 ,1 },
        { 1 ,0 ,1 ,1 },
    };
  
    cout << maxDecimalValue(mat, 0, 0, 0) << endl;
    return 0;
}

Java

// Java program to find maximum decimal value path in
// binary matrix
  
class GFG {
  
    static final int N = 4;
  
// Returns maximum decimal value in binary matrix.
// Here p indicate power of 2
    static int maxDecimalValue(int mat[][], int i, int j,
            int p) {
        // Out of matrix boundary
        if (i >= N || j >= N) {
            return 0;
        }
  
        int result = Math.max(maxDecimalValue(mat, i, j + 1, p + 1),
                maxDecimalValue(mat, i + 1, j, p + 1));
  
        // If current matrix value is 1 then return result +
        // power(2, p) else result
        if (mat[i][j] == 1) {
            return (int) (Math.pow(2, p) + result);
        } else {
            return result;
        }
    }
  
// Driver program 
    public static void main(String[] args) {
        int mat[][] = {{1, 1, 0, 1},
        {0, 1, 1, 0},
        {1, 0, 0, 1},
        {1, 0, 1, 1},};
  
        System.out.println(maxDecimalValue(mat, 0, 0, 0));
    }
}
//this code contributed by Rajput-Ji

Python3

# Python3 program to find maximum decimal
# value path in binary matrix
N =4
  
# Returns maximum decimal value in binary
# matrix. Here p indicate power of 2
def maxDecimalValue(mat, i, j, p):
  
    # Out of matrix boundary
    if i >= N or j >= N:
        return 0
          
    result = max(
        maxDecimalValue(mat, i, j+1, p+1),
        maxDecimalValue(mat, i+1, j, p+1))
  
    # If current matrix value is 1 then
    # return result + power(2, p) else
    # result
    if mat[i][j] == 1:
        return pow(2, p) + result
    else:
        return result
  
  
# Driver Program
mat = [ [1, 1, 0, 1],
        [0, 1, 1, 0],
        [1, 0, 0, 1],
        [1, 0, 1, 1] ]
  
print(maxDecimalValue(mat, 0, 0, 0))
  
# This code is contributed by Shrikant13.

C#

// C# program to find maximum decimal value path in
// binary matrix
  
using System;
class GFG {
  
    static int N = 4;
  
// Returns maximum decimal value in binary matrix.
// Here p indicate power of 2
    static int maxDecimalValue(int[,] mat, int i, 
                                int j,int p)
    {
        // Out of matrix boundary
        if (i >= N || j >= N) {
            return 0;
        }
  
        int result = Math.Max(maxDecimalValue(mat, i, j + 1, p + 1),
                    maxDecimalValue(mat, i + 1, j, p + 1));
  
        // If current matrix value is 1 then return result +
        // power(2, p) else result
        if (mat[i,j] == 1) 
        {
            return (int) (Math.Pow(2, p) + result);
        } else 
        {
            return result;
        }
    }
  
// Driver program 
    public static void Main() {
        int[,] mat = {{1, 1, 0, 1},
        {0, 1, 1, 0},
        {1, 0, 0, 1},
        {1, 0, 1, 1},};
  
        Console.Write(maxDecimalValue(mat, 0, 0, 0));
    }
}
// This code is contributed by Ita_c.

PHP

<?php
// PHP program to find maximum 
// decimal value path in binary
// matrix
  
// Returns maximum decimal value
// in binary matrix. Here p 
// indicate power of 2
function maxDecimalValue($mat, $i
                          $j, $p)
{
    $N=4;
      
    // Out of matrix boundary
    if ($i >= $N || $j >= $N )
        return 0;
  
    $result = max(maxDecimalValue($mat, $i
                            $j + 1, $p + 1),
                  maxDecimalValue($mat, $i + 1,
                                $j, $p + 1));
  
    // If current matrix value 
    // is 1 then return result +
    // power(2, p) else result
    if ($mat[$i][$j] == 1)
        return pow(2, $p) + $result;
    else
        return $result;
}
  
    // Driver Code
    $mat = array(array(1 ,1 ,0 ,1),
                 array(0 ,1 ,1 ,0),
                 array(1 ,0 ,0 ,1),
                 array(1 ,0 ,1 ,1));
  
    echo maxDecimalValue($mat, 0, 0, 0) ;
      
// This code is contributed by nitin mittal. 
?>

Output:

111

The time complexity of above recursive solution is exponential.

 Here matrix [3][3]               
            (2 2)
          /        
     (1 2)          (2 1)
    /             /     
 (0 2)   (1 1)   (1 1)   (2 1)
 /      /       /      /  
.    .  .    .    .   .   .  .
.    .  .    .    .   .   .  . and so no 

If we see recursion tree of above recursive solution, we can observe overlapping sub-problems. Since the problem has overlapping subproblems, we can solve it efficiently using Dynamic Programming. Below is Dynamic Programming based solution.

Below is the implementation of above problem using Dynamic Programming

C++

// C++ program to find Maximum decimal value Path in
// Binary matrix
#include<bits/stdc++.h>
using namespace std;
#define N 4
  
// Returns maximum decimal value in binary matrix.
// Here p indicate power of 2
long long int MaximumDecimalValue(int mat[][N], int n)
{
    int dp[n][n];
    memset(dp, 0, sizeof(dp));
    if (mat[0][0] == 1)
        dp[0][0] = 1 ; // 1*(2^0)
  
    // Compute binary stream of first row of matrix
    // and store result in dp[0][i]
    for (int i=1; i<n; i++)
    {
        // indicate 1*(2^i) + result of previous
        if (mat[0][i] == 1)
            dp[0][i] = dp[0][i-1] + pow(2, i);
  
        // indicate 0*(2^i) + result of previous
        else
            dp[0][i] = dp[0][i-1];
    }
  
    // Compute binary stream of first column of matrix
    // and store result in dp[i][0]
    for (int i = 1 ; i <n ; i++ )
    {
        // indicate 1*(2^i) + result of previous
        if (mat[i][0] == 1)
            dp[i][0] = dp[i-1][0] + pow(2, i);
  
        // indicate 0*(2^i) + result of previous
        else
            dp[i][0] = dp[i-1][0];
    }
  
    // Traversal rest Binary matrix and Compute maximum
    // decimal value
    for (int i=1 ; i < n ; i++ )
    {
        for (int j=1 ; j < n ; j++ )
        {
            // Here (i+j) indicate the current power of
            // 2 in path that is 2^(i+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 maximum decimal value in binary matrix
    return dp[n-1][n-1];
}
  
// Driver program
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;
}

Java

// Java program to find Maximum decimal value Path in
// Binary matrix
public class GFG {
  
    final static int N = 4;
// Returns maximum decimal value in binary matrix.
// Here p indicate power of 2
  
    static int MaximumDecimalValue(int mat[][], int n) {
        int dp[][] = new int[n][n];
        if (mat[0][0] == 1) {
            dp[0][0] = 1; // 1*(2^0)
        }
        // Compute binary stream of first row of matrix
        // and store result in dp[0][i]
        for (int i = 1; i < n; i++) {
            // indicate 1*(2^i) + result of previous
            if (mat[0][i] == 1) {
                dp[0][i] = (int) (dp[0][i - 1] + Math.pow(2, i));
            } // indicate 0*(2^i) + result of previous
            else {
                dp[0][i] = dp[0][i - 1];
            }
        }
  
        // Compute binary stream of first column of matrix
        // and store result in dp[i][0]
        for (int i = 1; i < n; i++) {
            // indicate 1*(2^i) + result of previous
            if (mat[i][0] == 1) {
                dp[i][0] = (int) (dp[i - 1][0] + Math.pow(2, i));
            } // indicate 0*(2^i) + result of previous
            else {
                dp[i][0] = dp[i - 1][0];
            }
        }
  
        // Traversal rest Binary matrix and Compute maximum
        // decimal value
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                // Here (i+j) indicate the current power of
                // 2 in path that is 2^(i+j)
                if (mat[i][j] == 1) {
                    dp[i][j] = (int) (Math.max(dp[i][j - 1], dp[i - 1][j])
                            + Math.pow(2, i + j));
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
  
        // Return maximum decimal value in binary matrix
        return dp[n - 1][n - 1];
    }
  
// Driver program
    public static void main(String[] args) {
  
        int mat[][] = {{1, 1, 0, 1},
        {0, 1, 1, 0},
        {1, 0, 0, 1},
        {1, 0, 1, 1},};
        System.out.println(MaximumDecimalValue(mat, 4));
    }
}
/*This code is contributed by Rajput-Ji*/

Python3

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

C#

// C# program to find Maximum decimal value Path in
// Binary matrix
using System;
public class GFG {
   
    readonly static int N = 4;
// Returns maximum decimal value in binary matrix.
// Here p indicate power of 2
   
    static int MaximumDecimalValue(int [,]mat, int n) {
        int [,]dp = new int[n,n];
        if (mat[0,0] == 1) {
            dp[0,0] = 1; // 1*(2^0)
        }
        // Compute binary stream of first row of matrix
        // and store result in dp[0,i]
        for (int i = 1; i < n; i++) {
            // indicate 1*(2^i) + result of previous
            if (mat[0,i] == 1) {
                dp[0,i] = (int) (dp[0,i - 1] + Math.Pow(2, i));
            } // indicate 0*(2^i) + result of previous
            else {
                dp[0,i] = dp[0,i - 1];
            }
        }
   
        // Compute binary stream of first column of matrix
        // and store result in dp[i,0]
        for (int i = 1; i < n; i++) {
            // indicate 1*(2^i) + result of previous
            if (mat[i,0] == 1) {
                dp[i,0] = (int) (dp[i - 1,0] + Math.Pow(2, i));
            } // indicate 0*(2^i) + result of previous
            else {
                dp[i,0] = dp[i - 1,0];
            }
        }
   
        // Traversal rest Binary matrix and Compute maximum
        // decimal value
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                // Here (i+j) indicate the current power of
                // 2 in path that is 2^(i+j)
                if (mat[i,j] == 1) {
                    dp[i,j] = (int) (Math.Max(dp[i,j - 1], dp[i - 1,j])
                            + Math.Pow(2, i + j));
                } else {
                    dp[i,j] = Math.Max(dp[i,j - 1], dp[i - 1,j]);
                }
            }
        }
   
        // Return maximum decimal value in binary matrix
        return dp[n - 1,n - 1];
    }
   
// Driver program
    public static void Main() {
   
        int [,]mat = {{1, 1, 0, 1},
        {0, 1, 1, 0},
        {1, 0, 0, 1},
        {1, 0, 1, 1},};
        Console.Write(MaximumDecimalValue(mat, 4));
    }
}
  
// This code is contributed by Rajput-Ji


Output:

111

Time Complexity : O(n2)
Auxiliary space : O(n2)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter