Recuento de posibles rutas de Matrix dada que tiene Bitwise XOR igual a K

Dada una array N*M (N + M ≤ 40) mat[][] , cada celda tiene algún valor que va de 0 a 10 ¹⁸ y un número entero   K . Encuentre el recuento de todas las rutas posibles de modo que el XOR bit a bit de los elementos en una ruta sea igual a K . El movimiento solo está permitido en la dirección derecha y hacia abajo. 

Ejemplos:

Entrada: N = 3, M = 4, K= 2
mat[][] = { {1, 3, 3, 3},
                 {0, 3, 3, 2},
                 {3, 0, 1, 1} }
Salida: 5
Explicación:  Todos los caminos posibles son: 
(1,1)→(2,1)→(2,2)→(3,2)→(3,3)→(3,4) = 1^0 ^ 3^0^1^1 = 2
(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(3,4) = 1^0^3 ^0^1^1 = 2
(1,1)→(2,1)→(2,2)→(2,3)→(2,4)→(3,4) = 1^0^3^ 3^2^1 =2
(1,1)→(1,2)→(1,3)→(2,3)→(3,3)→(3,4) = 1^3^3^3 ^1^1 =2
(1,1)→(1,2)→(2,2)→(2,3)→(3,3)→(3,4) = 1^3^3^3^ 1^1 =2

Entrada: N = 3, M = 3, K =11
 mat[][] = { {2, 1, 5},
                  {7, 10, 0},
                  {12, 6, 4} }
Salida: 3
Explicación: Todo caminos posibles son: 
(1,1)→(2,1)→(3,1)→(3,2)→(3,3) = 2 ^ 7 ^12 ^ 6 ^4 =11
(1,1) →(2,1)→(2,2)→(2,3)→(3,3) = 2 ^ 7 ^ 10 ^ 0 ^4 =11
(1,1)→(1,2)→(2 ,2)→(3,2)→(3,3) = 2^1^10^ 6 ^ 4 = 11 

Enfoque ingenuo: el enfoque simple es recorrer todos los caminos posibles y verificar si el XOR de ese camino es igual a K o no. En esto, use el retroceso ya que en cualquier celda dada habrá dos opciones para ir a la derecha o hacia abajo y esto se convertiría en dos declaraciones recursivas en la solución de retroceso.

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
ll n, m, k;
vector<vector<ll>> mat;
 
// Backtracking to find the path count
void backtracking(ll i, ll j, ll zor, ll &ans)
{
    // If the bottom-right cell is reached
    if (i == n - 1 && j == m - 1) {
         
        // If XOR value is k
        if (zor == k)
            ans++;
        return;
    }
 
    // Move rightwards
    if (j + 1 < m)
        backtracking(i, j + 1,
                     zor ^ mat[i][j + 1],
                     ans);
   
    // Move downwards
    if (i + 1 < n)
        backtracking(i + 1, j,
                     zor ^ mat[i + 1][j],
                     ans);
}
 
// Function to calculate all possible paths
int countPaths(int N, int M, int K)
{
    ll ans = 0;
    n = N; m = M; k = K;
    if (N == 1 && M == 1
        && mat[0][0] == K) {
        return 1;
    }
   
    // Calling the backtracking function
    backtracking(0, 0, mat[0][0], ans);
    return ans;
}
 
// Driver Code
int main()
{
    int N = 3, M = 3, K = 11;
    mat = { {2, 1, 5}, {7, 10, 0},
            {12, 6, 4} };
 
    // Function call
    int ans = countPaths(N, M, K);
    cout << ans << "\n";
    return 0;
}

// Java code to implement the above approach
import java.util.*;
 
class GFG{
 
  static int  n, m, k , ans;
  static int [][]mat;
 
  // Backtracking to find the path count
  static void backtracking(int i, int j, int zor)
  {
    // If the bottom-right ceint is reached
    if (i == n - 1 && j == m - 1) {
 
      // If XOR value is k
      if (zor == k)
        ans++;
      return;
    }
 
    // Move rightwards
    if (j + 1 < m)
      backtracking(i, j + 1,
                   zor ^ mat[i][j + 1]);
 
    // Move downwards
    if (i + 1 < n)
      backtracking(i + 1, j,
                   zor ^ mat[i + 1][j]);
  }
 
  // Function to calculate all possible paths
  static int countPaths(int N, int M, int K)
  {
    ans = 0;
    n = N; m = M; k = K;
    if (N == 1 && M == 1
        && mat[0][0] == K) {
      return 1;
    }
 
    // Calling the backtracking function
    backtracking(0, 0, mat[0][0]);
    return ans;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int N = 3, M = 3, K = 11;
    mat = new int[][]{ {2, 1, 5}, {7, 10, 0},
                      {12, 6, 4} };
 
    // Function call
    int ans = countPaths(N, M, K);
    System.out.print(ans+ "\n");
  }
}
 
// This code is contributed by 29AjayKumar

# Python program to find maximum sum in Binary Tree
mat = [[0 for i in range(2)]for j in range(2)]
n,m,k,ans = 0,0,0,0
 
# Backtracking to find the path count
def backtracking(i, j, zor):
 
    global ans
 
    # If the bottom-right ceis reached
    if (i == n - 1 and j == m - 1):
 
        # If XOR value is k
        if (zor == k):
            ans += 1
        return
 
    # Move rightwards
    if (j + 1 < m):
        backtracking(i, j + 1,zor ^ mat[i][j + 1])
 
    # Move downwards
    if (i + 1 < n):
        backtracking(i + 1, j,zor ^ mat[i + 1][j])
 
# Function to calculate all possible paths
def countPaths(N, M, K):
 
    global n,m,k,ans
 
    ans = 0
    n,m,k = N,M,K
    if (N == 1 and M == 1 and mat[0][0] == K):
        return 1
 
    # Calling the backtracking function
    backtracking(0, 0, mat[0][0])
    return ans
 
 
# Driver Code
N,M,K = 3,3,11
mat = [ [2, 1, 5], [7, 10, 0],
                    [12, 6, 4]]
 
# Function call
anss = countPaths(N, M, K)
print(anss)
 
# This code is contributed by shinjanpatra

// C# code to implement the above approach
using System;
 
class GFG{
 
  static int  n, m, k, ans;
 
  // Backtracking to find the path count
  static void backtracking(int i, int j, int zor, int [,]mat)
  {
    // If the bottom-right ceint is reached
    if (i == n - 1 && j == m - 1) {
 
      // If XOR value is k
      if (zor == k)
        ans++;
      return;
    }
 
    // Move rightwards
    if (j + 1 < m)
      backtracking(i, j + 1,
                   zor ^ mat[i, j + 1], mat);
 
    // Move downwards
    if (i + 1 < n)
      backtracking(i + 1, j,
                   zor ^ mat[i + 1, j], mat);
  }
 
  // Function to calculate all possible paths
  static int countPaths(int N, int M, int K, int [,]mat)
  {
    ans = 0;
    n = N; m = M; k = K;
    if (N == 1 && M == 1
        && mat[0, 0] == K) {
      return 1;
    }
 
    // Calling the backtracking function
    backtracking(0, 0, mat[0, 0], mat);
    return ans;
  }
 
  // Driver Code
  public static void Main()
  {
    int N = 3, M = 3, K = 11;
    int [,]mat = { {2, 1, 5}, {7, 10, 0},
                      {12, 6, 4} };
 
    // Function call
    int ans = countPaths(N, M, K, mat);
    Console.Write(ans+ "\n");
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript program to implement above approach
 
  let  n, m, k , ans;
 var mat = new Array(2);
  
// Loop to create 2D array using 1D array
for (var i = 0; i < mat.length; i++) {
    mat[i] = new Array(2);
}
 
  // Backtracking to find the path count
  function backtracking(i, j, zor)
  {
    // If the bottom-right celet is reached
    if (i == n - 1 && j == m - 1) {
 
      // If XOR value is k
      if (zor == k)
        ans++;
      return;
    }
 
    // Move rightwards
    if (j + 1 < m)
      backtracking(i, j + 1,
                   zor ^ mat[i][j + 1]);
 
    // Move downwards
    if (i + 1 < n)
      backtracking(i + 1, j,
                   zor ^ mat[i + 1][j]);
  }
 
  // Function to calculate all possible paths
  function countPaths(N, M, K)
  {
    ans = 0;
    n = N; m = M; k = K;
    if (N == 1 && M == 1
        && mat[0][0] == K) {
      return 1;
    }
 
    // Calling the backtracking function
    backtracking(0, 0, mat[0][0]);
    return ans;
  }
 
    // Driver Code
    let N = 3, M = 3, K = 11;
    mat = [ [2, 1, 5], [7, 10, 0],
                      [12, 6, 4]];
 
    // Function call
    let anss = countPaths(N, M, K);
    document.write(anss);
 
// This code iscontributed by sanjoy_62.
</script>

3

Complejidad de Tiempo: O(2 ^X * X) donde X = (N + M – 2)
Espacio Auxiliar: O(1)

¿Por qué simplemente retroceder fallaría aquí?
El número de movimientos necesarios para pasar de ( 1, 1) a (N, M) será igual a (N+M-2) . Ahora, utilizando una solución recursiva de seguimiento inverso, tomará O(2 ^(N+M-2) ) tiempo iterar sobre todas las rutas de esta longitud y verificar si cada ruta tiene XOR igual a K o no. Para valores más altos de (N+M) , este algoritmo consume mucho tiempo ya que el valor se acerca a la restricción proporcionada aquí.

Enfoque eficiente: usando el algoritmo Meet in The Middle divida el número de pasos y haga (N + M – 2)/2 en la primera mitad, descanse los pasos en la siguiente mitad. Siga los pasos que se mencionan a continuación para resolver el problema:

• Y combine las respuestas de las dos soluciones, que es básicamente la idea estándar del algoritmo Meet in the Middle.
• Divida esta máscara de n+m−2 bits en dos partes, mid = (n+m−2)/2 bits y (n+m−2)−mid bits.
• Para la parte izquierda: 
  • Realice un retroceso recursivo comenzando desde la celda (1,1) y hacia abajo y mantenga xor de la ruta para los pasos intermedios. después de los pasos intermedios , tenemos la posición del índice, es decir (i,j) y el valor de xor hasta este punto, y calculamos cuántos tripletes salen {zor, i,j}
• Para la parte derecha: 
  • Realice un retroceso recursivo comenzando desde la celda (N, M) y hacia la izquierda o hacia arriba y mantenga xor de la ruta para
     (N+M-2) – mediados de -1 pasos.
• después de los pasos intermedios , se encuentra la posición del índice, es decir, (i,j) y el valor xor hasta este punto, y se calcula cuántos de esos tripletes salen {zor, i,j}
• Después de escribir el código para ambas partes, ahora recorra los tripletes de la segunda parte y verifique si en un paso, es decir, (i-1, j) o (j-1, i) tenemos un triplete que tiene x o K en los tripletes de la parte izquierda.

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
ll n, m, k;
vector<vector<ll>> a;
ll cnt1 = 0, cnt2 = 0;
map<pair<ll, pair<ll, ll> >, ll> mp1, mp2;
 
// Backtracking function for the left part
void part1(ll i, ll j, ll cnt, ll zor)
{
    if (cnt <= 0) {
         
        // Count the number of triplets
        mp1[{ zor, { i, j } }]++;
        return;
    }
 
    // Move rightwards
    if (j + 1 < m) {
        part1(i, j + 1, cnt - 1,
              zor ^ a[i][j + 1]);
    }
   
    // Move downwards
    if (i + 1 < n)
        part1(i + 1, j, cnt - 1,
              zor ^ a[i + 1][j]);
}
 
// Backtracking function for the right part
void part2(ll i, ll j, ll cnt, ll zor)
{
    if (cnt <= 0) {
         
        // Count the number of triplets
        mp2[{ zor, { i, j } }]++;
        return;
    }
 
    // Move leftwards
    if (j - 1 >= 0) {
        part2(i, j - 1, cnt - 1,
              zor ^ a[i][j - 1]);
    }
   
    // Move upwards
    if (i - 1 >= 0)
        part2(i - 1, j, cnt - 1,
              zor ^ a[i - 1][j]);
}
 
// Function to count the paths with xor K
int countPaths(int N, int M, int K)
{
    ll ans = 0;
    n = N; m = M; k = K;
     
    // Number of steps for left part
    cnt1 = (n + m - 2) / 2;
 
    // NUmber of steps for right part
    cnt2 = (n + m - 2) - cnt1;
 
    // number of steps in both parts are 0
    if (n == 1 && m == 1 && a[0][0] == k) {
        return 1;
    }
 
    // Calling the recursive function
    // for the left and right part
    part1(0, 0, cnt1, a[0][0]);
    part2(n - 1, m - 1, cnt2 - 1,
          a[n - 1][m - 1]);
 
    // mp2 contains triplet of right part so
    // traverse the triplets of right part
    for (auto i : mp2) {
 
        // Extracting all elements
        // from the triplet
        ll zor = i.first.first;
        ll idx = i.first.second.first;
        ll j = i.first.second.second;
        ll cnt = i.second;
 
        // XOR OF RIGHT SIDE IS zor ,
        // then Xor of left side
        // must be zor^k such that Xor
        // of the total path is K
        ll required = k ^ zor;
 
        // Checking if one index to the left
        // are left triplet as how many paths
        if ((idx - 1) >= 0
            && mp1.find({ required,
                         { idx - 1, j } })
                   != mp1.end()) {
 
            // Total path would be paths
            // in left * paths in right
            ans += (cnt
                    * mp1[{ required,
                           { idx - 1, j } }]);
        }
 
        // Checking if one index upwards
        // are left triplet as how many paths
        if ((j - 1) >= 0
            && mp1.find({ required,
                         { idx, j - 1 } })
                   != mp1.end()) {
             
            // Total path would be paths
            // in left * paths in right
            ans += (cnt
                    * mp1[{ required,
                           { idx, j - 1 } }]);
        }
    }
    return ans;
}
 
// Driver Code
int main()
{
    int N = 3, M = 3, K = 11;
    a = { {2, 1, 5}, {7, 10, 0},
            {12, 6, 4} };
     
    int ans = countPaths(N, M, K);
    cout << ans;
    return 0;
}

3

Complejidad de tiempo: O(X * 2 ^X ) donde X = (N + M – 2)/2
Espacio auxiliar: O(N + M)