Recuento de formas de atravesar Matrix y volver al origen en K pasos

Posted on by Rudeus Greyrat

Dados tres enteros N , M y K , donde N y M son las dimensiones de la array y K son los pasos máximos posibles, la tarea es contar el número de formas de comenzar desde (0, 0) y regresar atravesando la array usando Solo pasos K. 
Nota: En cada paso, uno puede moverse hacia arriba, hacia abajo, hacia la izquierda, hacia la derecha o permanecer en la posición actual. La respuesta puede ser grande, así que imprima la respuesta módulo 10 9 + 7
Ejemplos: 
 

Entrada: N = 2, M = 2, K = 2 
Salida: 3 
Explicación: Las 
tres formas son: 
1) Permanecer, Permanecer. 
2) Arriba, Abajo 
3) Derecha, Izquierda
Entrada: N = 3, M = 3, K = 4 
Salida: 23 
 

Enfoque: El problema también se puede resolver usando la técnica de Memoización . Siga los pasos a continuación para resolver el problema: 
 

  • Comenzando desde la posición (0, 0), llame recursivamente a todas las posiciones posibles y disminuya el valor de los pasos en 1. 
     
  • Cree una array 3D de tamaño N * M * K ( DP[N][M][S] ) 
     
Possible ways for each step
can be calculated by:

 DP[i][j][k]
  =  Recursion(i+1, j, k-1)  +
     Recursion(i-1, j, k-1)  +  
     Recursion(i, j-1, k-1)  +  
     Recursion(i, j+1, k-1)  +  
     Recursion(i, j, k-1).

With base condition returning 0,
whenever
i >= l or i = b or j < 0 or k < 0.

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

C++

// C++ program to count total
// number of ways to return
// to origin after completing
// given number of steps.
 
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
 
long long dp[101][101][101];
int N, M, K;
 
// Function Initialize dp[][][]
// array with -1
void Initialize()
{
 
    for (int i = 0; i <= 100; i++)
        for (int j = 0; j <= 100; j++)
            for (int z = 0; z <= 100; z++)
                dp[i][j][z] = -1;
}
 
// Function returns the total count
int CountWays(int i, int j, int k)
{
    if (i >= N || i < 0
        || j >= M || j < 0 || k < 0)
        return 0;
 
    if (i == 0 && j == 0
        && k == 0)
        return 1;
 
    if (dp[i][j][k] != -1)
        return dp[i][j][k];
    else
        dp[i][j][k]
            = (CountWays(i + 1, j, k - 1) % MOD
               + CountWays(i - 1, j, k - 1) % MOD
               + CountWays(i, j - 1, k - 1) % MOD
               + CountWays(i, j + 1, k - 1) % MOD
               + CountWays(i, j, k - 1) % MOD)
              % MOD;
 
    return dp[i][j][k];
}
 
// Driver Program
int main()
{
    N = 3;
    M = 3;
    K = 4;
 
    Initialize();
    cout << CountWays(0, 0, K)
         << "\n";
 
    return 0;
}

Java

// Java program to count total
// number of ways to return
// to origin after completing
// given number of steps.
class GFG{
     
static int [][][] dp = new int[101][101][101];
static int N, M, K;
static int MOD = 1000000007;
     
// Function Initialize dp[][][]
// array with -1
public static void Initialize()
{
    for(int i = 0; i <= 100; i++)
       for(int j = 0; j <= 100; j++)
          for(int z = 0; z <= 100; z++)
             dp[i][j][z] = -1;
}
     
// Function returns the total count
public static int CountWays(int i, int j, int k)
{
    if (i >= N || i < 0 ||
        j >= M || j < 0 || k < 0)
        return 0;
     
    if (i == 0 && j == 0 && k == 0)
        return 1;
     
    if (dp[i][j][k] != -1)
        return dp[i][j][k];
     
    else
        dp[i][j][k] = (CountWays(i + 1, j, k - 1) % MOD +
                       CountWays(i - 1, j, k - 1) % MOD +
                       CountWays(i, j - 1, k - 1) % MOD +
                       CountWays(i, j + 1, k - 1) % MOD +
                       CountWays(i, j, k - 1) % MOD) % MOD;
     
    return dp[i][j][k];
}
 
// Driver code
public static void main(String[] args)
{
    N = 3;
    M = 3;
    K = 4;
     
    Initialize();
    System.out.println(CountWays(0, 0, K));
}
}
 
// This code is contributed by grand_master

Python3

# Python3 program to count total
# number of ways to return
# to origin after completing
# given number of steps.
MOD = 1000000007
 
dp = [[[0 for i in range(101)]
          for i in range(101)]
          for i in range(101)]
N, M, K = 0, 0, 0
 
# Function Initialize dp[][][]
# array with -1
def Initialize():
 
    for i in range(101):
        for j in range(101):
            for z in range(101):
                dp[i][j][z] = -1
 
# Function returns the total count
def CountWays(i, j, k):
 
    if (i >= N or i < 0 or
        j >= M or j < 0 or k < 0):
        return 0
 
    if (i == 0 and j == 0 and k == 0):
        return 1
 
    if (dp[i][j][k] != -1):
        return dp[i][j][k]
    else:
        dp[i][j][k] = (CountWays(i + 1, j, k - 1) % MOD +
                       CountWays(i - 1, j, k - 1) % MOD +
                       CountWays(i, j - 1, k - 1) % MOD +
                       CountWays(i, j + 1, k - 1) % MOD +
                       CountWays(i, j, k - 1) % MOD) % MOD
    return dp[i][j][k]
 
# Driver code
if __name__ == '__main__':
     
    N = 3
    M = 3
    K = 4
 
    Initialize()
    print(CountWays(0, 0, K))
 
# This code is contributed by mohit kumar 29

C#

// C# program to count total
// number of ways to return
// to origin after completing
// given number of steps.
using System;
 
class GFG{
     
static int [,,] dp = new int[101, 101, 101];
static int N, M, K;
static int MOD = 1000000007;
     
// Function Initialize [,]dp[]
// array with -1
public static void Initialize()
{
    for(int i = 0; i <= 100; i++)
        for(int j = 0; j <= 100; j++)
            for(int z = 0; z <= 100; z++)
                dp[i, j, z] = -1;
}
     
// Function returns the total count
public static int CountWays(int i, int j, int k)
{
    if (i >= N || i < 0 ||
        j >= M || j < 0 || k < 0)
        return 0;
     
    if (i == 0 && j == 0 && k == 0)
        return 1;
     
    if (dp[i, j, k] != -1)
        return dp[i, j, k];
     
    else
        dp[i, j, k] = (CountWays(i + 1, j, k - 1) % MOD +
                       CountWays(i - 1, j, k - 1) % MOD +
                       CountWays(i, j - 1, k - 1) % MOD +
                       CountWays(i, j + 1, k - 1) % MOD +
                       CountWays(i, j, k - 1) % MOD) % MOD;
     
    return dp[i, j, k];
}
 
// Driver code
public static void Main(String[] args)
{
    N = 3;
    M = 3;
    K = 4;
     
    Initialize();
    Console.WriteLine(CountWays(0, 0, K));
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// JavaScript program to count total
// number of ways to return
// to origin after completing
// given number of steps.
 
var MOD =  1000000007;
 
var dp = Array.from(Array(101), ()=>Array(101));
for(var i =0; i<101; i++)
        for(var j =0; j<101; j++)
            dp[i][j] = new Array(101).fill(-1);
var N, M, K;
 
// Function returns the total count
function CountWays(i, j, k)
{
    if (i >= N || i < 0
        || j >= M || j < 0 || k < 0)
        return 0;
 
    if (i == 0 && j == 0
        && k == 0)
        return 1;
 
    if (dp[i][j][k] != -1)
        return dp[i][j][k];
    else
        dp[i][j][k]
            = (CountWays(i + 1, j, k - 1) % MOD
               + CountWays(i - 1, j, k - 1) % MOD
               + CountWays(i, j - 1, k - 1) % MOD
               + CountWays(i, j + 1, k - 1) % MOD
               + CountWays(i, j, k - 1) % MOD)
              % MOD;
 
    return dp[i][j][k];
}
 
// Driver Program
N = 3;
M = 3;
K = 4;
document.write( CountWays(0, 0, K))
 
 
</script>
Producción: 

23

 

Publicación traducida automáticamente

Artículo escrito por Saif Haider y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *