Número de formas de llegar al final de la array con un valor AND distinto de cero

Dada una array N * N arr[][] que consta de enteros no negativos, la tarea es encontrar el número de formas de llegar a arr[N – 1][N – 1] con un valor AND distinto de cero a partir de la arr[0][0] yendo hacia abajo o hacia la derecha en cada movimiento. Cada vez que se alcanza una celda arr[i][j] , el valor ‘AND’ se actualiza como currentVal & arr[i][j] .

Ejemplos: 

Entrada: arr[][] = { 
{1, 1, 1}, 
{1, 1, 1}, 
{1, 1, 1}}
Salida: 6 
Todas las rutas darán un valor distinto de cero. 
Por lo tanto, el número de vías es igual a 6.
Entrada: arr[][] = { 
{1, 1, 2}, 
{1, 2, 1}, 
{2, 1, 1}} 
Salida: 0  

Enfoque: Este problema se puede resolver mediante programación dinámica . Primero, necesitamos decidir los estados del DP. Para cada celda arr[i][j] y un número X , almacenaremos el número de formas de llegar al arr[N – 1][N – 1] desde arr[i][j] con distinto de cero AND donde X es el valor AND de la ruta hasta ahora. Por lo tanto, nuestra solución utilizará programación dinámica tridimensional, dos para las coordenadas de las celdas y una para X.
La relación de recurrencia requerida es: 

dp[i][j][X] = dp[i][j + 1][X & arreglo[i][j]] + dp[i + 1][j][X & arreglo[i][j ]]  

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

// C++ implementation of the approach
#include <bits/stdc++.h>
#define n 3
#define maxV 20
using namespace std;
 
// 3d array to store
// states of dp
int dp[n][n][maxV];
 
// Array to determine whether
// a state has been solved before
int v[n][n][maxV];
 
// Function to return the count of required paths
int countWays(int i, int j, int x, int arr[][n])
{
 
    // Base cases
    if (i == n || j == n)
        return 0;
 
    x = (x & arr[i][j]);
    if (x == 0)
        return 0;
 
    if (i == n - 1 && j == n - 1)
        return 1;
 
    // If a state has been solved before
    // it won't be evaluated again
    if (v[i][j][x])
        return dp[i][j][x];
 
    v[i][j][x] = 1;
 
    // Recurrence relation
    dp[i][j][x] = countWays(i + 1, j, x, arr)
                  + countWays(i, j + 1, x, arr);
 
    return dp[i][j][x];
}
 
// Driver code
int main()
{
    int arr[n][n] = { { 1, 2, 1 },
                      { 1, 1, 0 },
                      { 2, 1, 1 } };
 
    cout << countWays(0, 0, arr[0][0], arr);
 
    return 0;
}

// Java implementation of the approach
class GFG {
 
    static int n = 3;
    static int maxV = 20;
 
    // 3d array to store
    // states of dp
    static int[][][] dp = new int[n][n][maxV];
 
    // Array to determine whether
    // a state has been solved before
    static int[][][] v = new int[n][n][maxV];
 
    // Function to return the count of required paths
    static int countWays(int i, int j,
                         int x, int arr[][])
    {
 
        // Base cases
        if (i == n || j == n) {
            return 0;
        }
 
        x = (x & arr[i][j]);
        if (x == 0) {
            return 0;
        }
 
        if (i == n - 1 && j == n - 1) {
            return 1;
        }
 
        // If a state has been solved before
        // it won't be evaluated again
        if (v[i][j][x] == 1) {
            return dp[i][j][x];
        }
 
        v[i][j][x] = 1;
 
        // Recurrence relation
        dp[i][j][x] = countWays(i + 1, j, x, arr)
                      + countWays(i, j + 1, x, arr);
 
        return dp[i][j][x];
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[][] = { { 1, 2, 1 },
                        { 1, 1, 0 },
                        { 2, 1, 1 } };
 
        System.out.println(countWays(0, 0, arr[0][0], arr));
    }
}
 
// This code contributed by Rajput-Ji

# Python3 implementation of the approach
n = 3
maxV = 20
 
# 3d array to store states of dp
dp = [[[0 for i in range(maxV)]
          for i in range(n)]
          for i in range(n)]
 
# Array to determine whether
# a state has been solved before
v = [[[0 for i in range(maxV)]
         for i in range(n)]
         for i in range(n)]
 
# Function to return
# the count of required paths
def countWays(i, j, x, arr):
 
    # Base cases
    if (i == n or j == n):
        return 0
 
    x = (x & arr[i][j])
    if (x == 0):
        return 0
 
    if (i == n - 1 and j == n - 1):
        return 1
 
    # If a state has been solved before
    # it won't be evaluated again
    if (v[i][j][x]):
        return dp[i][j][x]
 
    v[i][j][x] = 1
 
    # Recurrence relation
    dp[i][j][x] = countWays(i + 1, j, x, arr) + \
                  countWays(i, j + 1, x, arr);
 
    return dp[i][j][x]
 
# Driver code
arr = [[1, 2, 1 ],
       [1, 1, 0 ],
       [2, 1, 1 ]]
 
print(countWays(0, 0, arr[0][0], arr))
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
 
class GFG
{
 
    static int n = 3;
    static int maxV = 20;
 
    // 3d array to store
    // states of dp
    static int[,,] dp = new int[n, n, maxV];
 
    // Array to determine whether
    // a state has been solved before
    static int[,,] v = new int[n, n, maxV];
 
    // Function to return the count of required paths
    static int countWays(int i, int j,
                        int x, int [,]arr)
    {
 
        // Base cases
        if (i == n || j == n)
        {
            return 0;
        }
 
        x = (x & arr[i, j]);
        if (x == 0)
        {
            return 0;
        }
 
        if (i == n - 1 && j == n - 1)
        {
            return 1;
        }
 
        // If a state has been solved before
        // it won't be evaluated again
        if (v[i, j, x] == 1)
        {
            return dp[i, j, x];
        }
 
        v[i, j, x] = 1;
 
        // Recurrence relation
        dp[i, j, x] = countWays(i + 1, j, x, arr)
                    + countWays(i, j + 1, x, arr);
 
        return dp[i, j, x];
    }
 
    // Driver code
    public static void Main()
    {
        int [,]arr = { { 1, 2, 1 },
                        { 1, 1, 0 },
                        { 2, 1, 1 } };
 
    Console.WriteLine(countWays(0, 0, arr[0,0], arr));
    }
}
 
// This code is contributed by AnkitRai01

<script>
 
// Javascript implementation of the approach
var n = 3;
var maxV = 20;
 
// 3d array to store
// states of dp
var dp = new Array(n);
 
for(var i = 0; i<n; i++)
{
    dp[i] = new Array(n);
    for(var j =0; j<n;j++)
    {
        dp[i][j] = new Array(maxV);
    }
}
 
var v = new Array(n);
 
// Array to determine whether
// a state has been solved before
for(var i = 0; i<n; i++)
{
    v[i] = new Array(n);
    for(var j =0; j<n;j++)
    {
        v[i][j] = new Array(maxV);
    }
}
 
// Function to return the count of required paths
function countWays(i, j, x, arr)
{
 
    // Base cases
    if (i == n || j == n)
        return 0;
 
    x = (x & arr[i][j]);
    if (x == 0)
        return 0;
 
    if (i == n - 1 && j == n - 1)
        return 1;
 
    // If a state has been solved before
    // it won't be evaluated again
    if (v[i][j][x])
        return dp[i][j][x];
 
    v[i][j][x] = 1;
 
    // Recurrence relation
    dp[i][j][x] = countWays(i + 1, j, x, arr)
                  + countWays(i, j + 1, x, arr);
 
    return dp[i][j][x];
}
 
// Driver code
var arr = [ [ 1, 2, 1 ],
                  [ 1, 1, 0 ],
                  [ 2, 1, 1 ] ];
document.write( countWays(0, 0, arr[0][0], arr));
 
 
</script>

1

Complejidad temporal: O(n ² )

Espacio Auxiliar: O(n ⁴ * maxV)