Dada una array , mat[][] de dimensiones N * M , la tarea es imprimir el valor XOR bit a bit máximo que se puede obtener para una ruta desde la celda superior izquierda (0, 0) hasta la celda inferior derecha ( N – 1, M – 1) de la array dada. Los únicos movimientos posibles desde cualquier celda (i, j) son (i + 1, j) y (i, j + 1) .
Nota: El valor XOR bit a bit de una ruta se define como el XOR bit a bit de todos los elementos posibles en esa ruta.
Ejemplos:
Entrada: mat[][] = {{3, 2, 1}, {6, 5, 4}, {7, 8, 9}}
Salida: 13
Explicación: Rutas
posibles de (0, 0) a (N – 1, M – 1) y sus valores XOR bit a bit son:
(0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2) con valor XOR 13 (0 ,
0) -> (0, 1) -> (1, 1) -> (1, 2) -> (2, 2) con valor XOR 9.
(0, 0) -> (1, 0 ) -> (1, 1) -> (1, 2) -> (2, 2) con valor XOR 13.
(0, 0) -> (0, 1) -> (1, 1) -> (2 , 1) -> (2, 2) con valor XOR 5.
(0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (2, 2) con valor XOR valor 1.
(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) con valor XOR 3
Por lo tanto, el valor XOR bit a bit máximo para todos los posibles caminos es 13.
Entrada: mat[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
Salida: 15
Enfoque: La idea es generar todas las rutas posibles desde la celda superior izquierda (0, 0) hasta la celda inferior derecha (N – 1, M – 1) de la array dada usando Recursión e imprimir el valor XOR máximo de todos. caminos posibles. Las siguientes son las relaciones de recurrencia y sus casos base:
Relación de recurrencia:
printMaxXOR(i, j, xorValue) = max(printMaxXOR(i – 1, j, xorValue ^ mat[i][j]), printMaxXOR(i, j – 1, xorValue ^ mat[i][j] ))Caso base:
si i = 0 y j = 0: devuelve mat[i][j] ^ xorValue
si i = 0: devuelve printMaxXOR(i, j – 1, mat[i][j] ^ xorValue)
si j = 0 : devuelve imprimirMaxXOR(i – 1, j, mat[i][j] ^ xorValue)
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, diga xorValue para almacenar el XOR bit a bit de todos los elementos posibles en la ruta desde la celda superior izquierda (0, 0) hasta la celda inferior derecha (N – 1, M – 1) .
- Utilice la relación de recurrencia anterior para encontrar el valor XOR máximo de todas las rutas posibles desde la celda superior izquierda (0, 0) hasta la celda inferior derecha (N – 1, M – 1) .
- Finalmente, imprima el valor XOR máximo de todas las rutas posibles desde la celda superior izquierda (0, 0) hasta la celda inferior derecha (N – 1, M – 1) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print maximum XOR
// value of all possible path
// from (0, 0) to (N - 1, M - 1)
int printMaxXOR(vector<vector<int> >& mat,
int i, int j,
int xorValue)
{
// Base case
if (i == 0 && j == 0) {
return mat[i][j] ^ xorValue;
}
// Base case
if (i == 0) {
// Stores maximum XOR value
// by selecting path from (i, j)
// to (i, j - 1)
return printMaxXOR(mat, i, j - 1,
mat[i][j] ^ xorValue);
}
if (j == 0) {
// Stores maximum XOR value
// by selecting path from (i, j)
// to (i - 1, j)
return printMaxXOR(mat, i - 1, j,
mat[i][j] ^ xorValue);
}
// Stores maximum XOR value
// by selecting path from (i, j)
// to (i - 1, j)
int X
= printMaxXOR(mat, i - 1,
j, mat[i][j] ^ xorValue);
// Stores maximum XOR value
// by selecting path from (i, j)
// to (i, j - 1)
int Y
= printMaxXOR(mat, i, j - 1,
mat[i][j] ^ xorValue);
return max(X, Y);
}
// Driver Code
int main()
{
vector<vector<int> > mat
= { { 3, 2, 1 },
{ 6, 5, 4 },
{ 7, 8, 9 } };
int N = mat.size();
int M = mat[0].size();
// Stores bitwise XOR of
// all elements on each possible path
int xorValue = 0;
cout << printMaxXOR(mat, N - 1,
M - 1, xorValue);
}
Java
import java.io.*;
import java.util.*;
class GFG {
public static int printMaxXOR(int[][] mat,
int i, int j,
int xorValue)
{
// Base case
if (i == 0 && j == 0)
{
return mat[i][j] ^ xorValue;
}
// Base case
if (i == 0) {
// Stores maximum XOR value
// by selecting path from (i, j)
// to (i, j - 1)
return printMaxXOR(mat, i,
j - 1,
mat[i][j] ^ xorValue);
}
if (j == 0) {
// Stores maximum XOR value
// by selecting path from (i, j)
// to (i - 1, j)
return printMaxXOR(mat,
i - 1, j,
mat[i][j] ^ xorValue);
}
// Stores maximum XOR value
// by selecting path from (i, j)
// to (i - 1, j)
int X = printMaxXOR(mat,
i - 1, j,
mat[i][j] ^ xorValue);
// Stores maximum XOR value
// by selecting path from (i, j)
// to (i, j - 1)
int Y = printMaxXOR(mat,
i, j - 1,
mat[i][j] ^ xorValue);
return Math.max(X, Y);
}
// Driver Code
public static void main(String[] args)
{
int[][] mat
= { { 3, 2, 1 },
{ 6, 5, 4 },
{ 7, 8, 9 } };
int N = mat.length;
int M = mat[0].length;
// Stores bitwise XOR of
// all elements on each possible path
int xorValue = 0;
System.out.println(
printMaxXOR(mat, N - 1, M - 1, xorValue));
}
// This code is contributed by hemanth gadarla
}
Python3
# Python 3 program to implement # the above approach # Function to print maximum XOR # value of all possible path # from (0, 0) to (N - 1, M - 1) def printMaxXOR(mat, i, j, xorValue): # Base case if (i == 0 and j == 0): return mat[i][j] ^ xorValue # Base case if (i == 0): # Stores maximum XOR value # by selecting path from (i, j) # to (i, j - 1) return printMaxXOR(mat, i, j - 1, mat[i][j] ^ xorValue) if (j == 0): # Stores maximum XOR value # by selecting path from (i, j) # to (i - 1, j) return printMaxXOR(mat, i - 1, j, mat[i][j] ^ xorValue) # Stores maximum XOR value # by selecting path from (i, j) # to (i - 1, j) X = printMaxXOR(mat, i - 1, j, mat[i][j] ^ xorValue) # Stores maximum XOR value # by selecting path from (i, j) # to (i, j - 1) Y = printMaxXOR(mat, i, j - 1, mat[i][j] ^ xorValue) return max(X, Y) # Driver Code if __name__ == "__main__": mat = [[3, 2, 1], [6, 5, 4], [7, 8, 9]] N = len(mat) M = len(mat[0]) # Stores bitwise XOR of # all elements on each # possible path xorValue = 0 print(printMaxXOR(mat, N - 1, M - 1, xorValue)) # This code is contributed by Chitranayal
C#
// C# program to implement the
// above approach
using System;
class GFG{
public static int printMaxXOR(int[,] mat,
int i, int j,
int xorValue)
{
// Base case
if (i == 0 && j == 0)
{
return mat[i,j] ^
xorValue;
}
// Base case
if (i == 0)
{
// Stores maximum XOR value
// by selecting path from (i, j)
// to (i, j - 1)
return printMaxXOR(mat, i,
j - 1,
mat[i,j] ^
xorValue);
}
if (j == 0)
{
// Stores maximum XOR value
// by selecting path from (i, j)
// to (i - 1, j)
return printMaxXOR(mat,
i - 1, j,
mat[i,j] ^
xorValue);
}
// Stores maximum XOR value
// by selecting path from (i, j)
// to (i - 1, j)
int X = printMaxXOR(mat,
i - 1, j,
mat[i,j] ^
xorValue);
// Stores maximum XOR value
// by selecting path from (i, j)
// to (i, j - 1)
int Y = printMaxXOR(mat,
i, j - 1,
mat[i,j] ^
xorValue);
return Math.Max(X, Y);
}
// Driver Code
public static void Main(String[] args)
{
int[,] mat = {{3, 2, 1},
{6, 5, 4},
{7, 8, 9}};
int N = mat.GetLength(0);
int M = mat.GetLength(1);
// Stores bitwise XOR of
// all elements on each
// possible path
int xorValue = 0;
Console.WriteLine(printMaxXOR(mat, N - 1,
M - 1,
xorValue));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program to implement
// the above approach
function printMaxXOR(mat, i, j, xorValue)
{
// Base case
if (i == 0 && j == 0)
{
return mat[i][j] ^ xorValue;
}
// Base case
if (i == 0) {
// Stores maximum XOR value
// by selecting path from (i, j)
// to (i, j - 1)
return printMaxXOR(mat, i,
j - 1,
mat[i][j] ^ xorValue);
}
if (j == 0) {
// Stores maximum XOR value
// by selecting path from (i, j)
// to (i - 1, j)
return printMaxXOR(mat,
i - 1, j,
mat[i][j] ^ xorValue);
}
// Stores maximum XOR value
// by selecting path from (i, j)
// to (i - 1, j)
let X = printMaxXOR(mat,
i - 1, j,
mat[i][j] ^ xorValue);
// Stores maximum XOR value
// by selecting path from (i, j)
// to (i, j - 1)
let Y = printMaxXOR(mat,
i, j - 1,
mat[i][j] ^ xorValue);
return Math.max(X, Y);
}
// Driver Code
let mat
= [[ 3, 2, 1 ],
[ 6, 5, 4 ],
[ 7, 8, 9 ]];
let N = mat.length;
let M = mat[0].length;
// Stores bitwise XOR of
// all elements on each possible path
let xorValue = 0;
document.write(
printMaxXOR(mat, N - 1, M - 1, xorValue));
</script>
Producción
13
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente : el enfoque anterior se puede optimizar mediante el uso de programación dinámica. La array bidimensional dp almacena valores de valor máximo que podemos obtener en esa fila y columna.
- dp[i][j]=max(dp[i-1][j]^mat[i][j] ,dp[i][j-1]^mat[i][j])
- El resultado final se almacena en dp[n-1][m-1]
- dp[i][j]=maxxor hasta la i-ésima fila y la j-ésima columna
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
#define N 3
#define M 3
int printMaxXOR(int mat[][N],
int n, int m)
{
int dp[n + 2][m + 2];
// Initialise dp 1st row
// and 1st column
for (int i = 0; i < n; i++)
dp[i][0] = ((i - 1 >= 0) ?
dp[i - 1][0] : 0) ^
mat[i][0];
for (int j = 0; j < m; j++)
dp[0][j] = ((j - 1 >= 0) ?
dp[0][j - 1] : 0) ^
mat[0][j];
// d[i][j] =maxXOr value you can
// get till ith row and jth column
for (int i = 1; i < n; i++)
{
for (int j = 1; j < m; j++)
{
// Find the maximum value You
// can get from the top (i-1,j)
// and left (i,j-1)
int X = mat[i][j] ^
dp[i - 1][j];
int Y = mat[i][j] ^
dp[i][j - 1];
dp[i][j] = max(X, Y);
}
}
// Return the maximum
// Xorvalue
return dp[n - 1][m - 1];
}
// Driver Code
int main()
{
int mat[M][N] = {{3, 2, 1},
{6, 5, 4},
{7, 8, 9}};
// Stores bitwise XOR of
// all elements on each
// possible path
int xorValue = 0;
cout << (printMaxXOR(mat,
N, M));
}
// This code is contributed by gauravrajput1
Java
import java.io.*;
import java.util.*;
class GFG {
public static int printMaxXOR(int[][] mat,
int n, int m)
{
int dp[][] = new int[n + 2][m + 2];
// Initialise dp 1st row and 1st column
for (int i = 0; i < n; i++)
dp[i][0] = ((i - 1 >= 0)
? dp[i - 1][0] : 0)
^ mat[i][0];
for (int j = 0; j < m; j++)
dp[0][j] = ((j - 1 >= 0)
? dp[0][j - 1] : 0)
^ mat[0][j];
// d[i][j] =maxXOr value you can
// get till ith row and jth column
for (int i = 1; i < n; i++)
{
for (int j = 1; j < m; j++)
{
// Find the maximum value You
// can get from the top (i-1,j)
// and left (i,j-1)
int X = mat[i][j] ^ dp[i - 1][j];
int Y = mat[i][j] ^ dp[i][j - 1];
dp[i][j] = Math.max(X, Y);
}
}
// Return the maximum Xorvalue
return dp[n - 1][m - 1];
}
// Driver Code
public static void main(String[] args)
{
int[][] mat
= { { 3, 2, 1 },
{ 6, 5, 4 },
{ 7, 8, 9 } };
int N = mat.length;
int M = mat[0].length;
// Stores bitwise XOR of
// all elements on each possible path
int xorValue = 0;
System.out.println(printMaxXOR(mat, N, M));
}
// This code is contributed by hemanth gadarla
}
Python3
# Python3 program for the # above approach def printMaxXOR(mat, n, m): dp = [[0 for i in range(m+2)] for j in range(n+2)]; # Initialise dp 1st row and # 1st column for i in range(n): if((i - 1) >= 0): dp[i][0] = (dp[i - 1][0] ^ mat[i][0]); else: dp[i][0] = 0 ^ mat[i][0]; for j in range(m): if((j - 1) >= 0): dp[0][j] = (dp[0][j - 1] ^ mat[0][j]); else: dp[0][j] = 0 ^ mat[0][j]; # d[i][j] = maxXOr value you can # get till ith row and jth column for i in range(1, n): for j in range(1, m): # Find the maximum value You # can get from the top (i-1,j) # and left (i,j-1) X = (mat[i][j] ^ dp[i - 1][j]); Y = (mat[i][j] ^ dp[i][j - 1]); dp[i][j] = max(X, Y); # Return the maximum # Xorvalue return dp[n - 1][m - 1]; # Driver Code if __name__ == '__main__': mat = [[3, 2, 1], [6, 5, 4], [7, 8, 9]]; N = len(mat); M = len(mat[0]); # Stores bitwise XOR of # all elements on each # possible path xorValue = 0; print(printMaxXOR(mat, N, M)); # This code is contributed by gauravrajput1
C#
// C# Program for the
// above approach
using System;
class GFG{
public static int printMaxXOR(int[,] mat,
int n, int m)
{
int [,]dp = new int[n + 2, m + 2];
// Initialise dp 1st row and
// 1st column
for (int i = 0; i < n; i++)
dp[i, 0] = ((i - 1 >= 0) ?
dp[i - 1, 0] : 0) ^
mat[i, 0];
for (int j = 0; j < m; j++)
dp[0, j] = ((j - 1 >= 0) ?
dp[0, j - 1] : 0) ^
mat[0, j];
// d[i,j] =maxXOr value you can
// get till ith row and jth column
for (int i = 1; i < n; i++)
{
for (int j = 1; j < m; j++)
{
// Find the maximum value You
// can get from the top (i-1,j)
// and left (i,j-1)
int X = mat[i, j] ^ dp[i - 1, j];
int Y = mat[i, j] ^ dp[i, j - 1];
dp[i, j] = Math.Max(X, Y);
}
}
// Return the maximum Xorvalue
return dp[n - 1, m - 1];
}
// Driver Code
public static void Main(String[] args)
{
int[,] mat = {{3, 2, 1},
{6, 5, 4},
{7, 8, 9}};
int N = mat.GetLength(0);
int M = mat.GetLength(1);
// Stores bitwise XOR of
// all elements on each
// possible path
int xorValue = 0;
Console.WriteLine(printMaxXOR(mat,
N, M));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for the above approach
N = 3;
M = 3;
function printMaxXOR(mat, n, m)
{
// var dp[n + 2][m + 2];
var dp = new Array(n+2).fill(0).map(item =>(new Array(m+2).fill(0)));
// Initialise dp 1st row
// and 1st column
for (var i = 0; i < n; i++)
dp[i][0] = ((i - 1 >= 0) ? dp[i - 1][0] : 0) ^ mat[i][0];
for (var j = 0; j < m; j++)
dp[0][j] = ((j - 1 >= 0) ? dp[0][j - 1] : 0) ^ mat[0][j];
// d[i][j] =maxXOr value you can
// get till ith row and jth column
for (var i = 1; i < n; i++)
{
for (var j = 1; j < m; j++)
{
// Find the maximum value You
// can get from the top (i-1,j)
// and left (i,j-1)
var X = mat[i][j] ^ dp[i - 1][j];
var Y = mat[i][j] ^ dp[i][j - 1];
dp[i][j] = Math.max(X, Y);
}
}
// Return the maximum
// Xorvalue
return dp[n - 1][m - 1];
}
var mat = [[3, 2, 1],
[6, 5, 4],
[7, 8, 9]];
// Stores bitwise XOR of
// all elements on each
// possible path
var xorValue = 0;
document.write(printMaxXOR(mat, N, M));
//This code is contributed by SoumikMondal
</script>
Producción
13
Complejidad temporal: O(N*M)
Complejidad espacial auxiliar: O(N*M)
Publicación traducida automáticamente
Artículo escrito por ajaykr00kj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA