Dada una array cuadrada binaria [n*n]. Encuentre el valor entero máximo en una ruta de arriba a la izquierda a abajo a la derecha. Calculamos el valor entero usando bits de la ruta recorrida. Comenzamos en el índice [0,0] y terminamos en el índice [n-1][n-1]. del índice [i, j], podemos mover [i, j+1] o [i+1, j].
Ejemplos:
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) ->(3,3)
Decimal value : 1*(2^0) + 1*(2^1) + 1*(2^2) + 1*(2^3) +
0*(2^4) + 1*(2^5) + 1*(2^6) = 111
El problema anterior se puede definir recursivamente de la siguiente manera:
// 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
A continuación se muestra la implementación del algoritmo recursivo anterior.
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.
?>
Javascript
<script>
// JavaScript program to find maximum
// decimal value path in binary matrix
let N = 4;
// Returns maximum decimal value in
// binary matrix.Here p indicate power of 2
function maxDecimalValue(mat, i, j, p)
{
// Out of matrix boundary
if (i >= N || j >= N)
{
return 0;
}
let 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 (Math.pow(2, p) + result);
}
else
{
return result;
}
}
// Driver Code
let mat = [ [ 1, 1, 0, 1 ],
[ 0, 1, 1, 0 ],
[ 1, 0, 0, 1 ],
[ 1, 0, 1, 1 ] ];
document.write(maxDecimalValue(mat, 0, 0, 0));
// This code is contributed by souravghosh0416
</script>
Producción:
111
La complejidad temporal de la solución recursiva anterior es exponencial .
Here matrix [3][3]
(2 2)
/ \
(1 2) (2 1)
/ \ / \
(0 2) (1 1) (1 1) (2 1)
/ \ / \ / \ / \
. . . . . . . .
. . . . . . . . and so no
Si vemos el árbol de recurrencia de la solución recursiva anterior, podemos observar subproblemas superpuestos . Dado que el problema tiene subproblemas superpuestos, podemos resolverlo de manera eficiente utilizando Programación Dinámica. A continuación se muestra una solución basada en programación dinámica.
A continuación se muestra la implementación del problema anterior utilizando la programación dinámica
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
Javascript
<script>
// Javascript program to find Maximum decimal value Path in
// Binary matrix
let N = 4;
// Returns maximum decimal value in binary matrix.
// Here p indicate power of 2
function MaximumDecimalValue(mat,n)
{
let dp=new Array(n);
for(let i = 0; i < n; i++)
{
dp[i] = new Array(n);
for(let j = 0; j < n; j++)
{
dp[i][j] = 0;
}
}
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 (let i = 1; i < n; i++)
{
// indicate 1*(2^i) + result of previous
if (mat[0][i] == 1)
{
dp[0][i] = 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 (let i = 1; i < n; i++)
{
// indicate 1*(2^i) + result of previous
if (mat[i][0] == 1)
{
dp[i][0] = Math.floor(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 (let i = 1; i < n; i++)
{
for (let 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] = Math.floor(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
let mat = [[ 1 ,1 ,0 ,1 ],
[ 0 ,1 ,1 ,0 ],
[ 1 ,0 ,0 ,1 ],
[ 1 ,0 ,1 ,1 ]];
document.write(MaximumDecimalValue(mat, 4))
// This code is contributed by rag2127.
</script>
Producción:
111
Tiempo Complejidad : O(n 2 )
Espacio auxiliar : O(n 2 )
Este artículo es una contribución de Nishant_Singh (Pintu) . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA