Recuento de caminos posibles desde la parte superior izquierda hasta la parte inferior derecha de una array M x N moviéndose hacia la derecha, hacia abajo o en diagonal

Posted on by Rudeus Greyrat

Dados 2 enteros M y N, la tarea es encontrar el recuento de todos los caminos posibles desde la parte superior izquierda hasta la parte inferior derecha de una array M x N con las restricciones de que desde cada celda puede moverse solo hacia la derecha o hacia abajo o en diagonal

Ejemplos:

Entrada:  M = 3, N = 3
Salida: 13
Explicación: Hay 13 rutas de la siguiente manera: VVHH, VHVH, HVVH, DVH, VDH, VHHV, HVHV, DHV, HHVV, HDV, VHD, HVD y DD donde V representa vertical, H representa horizontal y D representa caminos diagonales.

Entrada:  M = 2, N = 2
Salida: 3

 

Enfoque: La idea es usar la recursividad para encontrar el número total de caminos. Este enfoque es muy similar al que se analiza en este artículo. Siga los pasos a continuación para resolver el problema:

  • Si M o N es igual a 1, devuelve 1.
  • De lo contrario, cree una función recursiva numberOfPaths() llame a la misma función para los valores {M-1, N}, {M, N-1} y {M-1, N-1} que representan el movimiento vertical, horizontal y diagonal respectivamente.

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

C++

// C++  program for the above approach
#include <iostream>
using namespace std;
 
// Returns count of possible paths to
// reach cell at row number M and column
// number N from the topmost leftmost
// cell (cell at 1, 1)
int numberOfPaths(int M, int N)
{
 
    // If either given row number or
    // given column number is first
    if (M == 1 || N == 1)
        return 1;
 
    // Horizontal Paths +
    // Vertical Paths +
    // Diagonal Paths
    return numberOfPaths(M - 1, N)
          + numberOfPaths(M, N - 1)
           + numberOfPaths(M - 1, N - 1);
}
 
// Driver Code
int main()
{
    cout << numberOfPaths(3, 3);
    return 0;
}

Java

// Java  program for the above approach
import java.util.*;
public class GFG
{
   
// Returns count of possible paths to
// reach cell at row number M and column
// number N from the topmost leftmost
// cell (cell at 1, 1)
static int numberOfPaths(int M, int N)
{
 
    // If either given row number or
    // given column number is first
    if (M == 1 || N == 1)
        return 1;
 
    // Horizontal Paths +
    // Vertical Paths +
    // Diagonal Paths
    return numberOfPaths(M - 1, N)
          + numberOfPaths(M, N - 1)
           + numberOfPaths(M - 1, N - 1);
}
 
// Driver Code
public static void main(String args[])
{
    System.out.print(numberOfPaths(3, 3));
 
}
}
 
// This code is contributed by Samim Hossain Mondal.

Python

# Python  program for the above approach
 
# Returns count of possible paths to
# reach cell at row number M and column
# number N from the topmost leftmost
# cell (cell at 1, 1)
def numberOfPaths(M, N):
 
    # If either given row number or
    # given column number is first
    if (M == 1 or N == 1):
        return 1
 
    # Horizontal Paths +
    # Vertical Paths +
    # Diagonal Paths
    return numberOfPaths(M - 1, N) \
        + numberOfPaths(M, N - 1) \
        + numberOfPaths(M - 1, N - 1)
 
# Driver Code
print(numberOfPaths(3, 3))
 
# This code is contributed by Samim Hossain Mondal.

C#

// C#  program for the above approach
using System;
 
public class GFG
{
   
// Returns count of possible paths to
// reach cell at row number M and column
// number N from the topmost leftmost
// cell (cell at 1, 1)
static int numberOfPaths(int M, int N)
{
 
    // If either given row number or
    // given column number is first
    if (M == 1 || N == 1)
        return 1;
 
    // Horizontal Paths +
    // Vertical Paths +
    // Diagonal Paths
    return numberOfPaths(M - 1, N)
          + numberOfPaths(M, N - 1)
           + numberOfPaths(M - 1, N - 1);
}
 
// Driver Code
public static void Main(String []args)
{
    Console.Write(numberOfPaths(3, 3));
 
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
       // JavaScript code for the above approach
 
       // Returns count of possible paths to
       // reach cell at row number M and column
       // number N from the topmost leftmost
       // cell (cell at 1, 1)
       function numberOfPaths(M, N) {
 
           // If either given row number or
           // given column number is first
           if (M == 1 || N == 1)
               return 1;
 
           // Horizontal Paths +
           // Vertical Paths +
           // Diagonal Paths
           return numberOfPaths(M - 1, N)
               + numberOfPaths(M, N - 1)
               + numberOfPaths(M - 1, N - 1);
       }
 
       // Driver Code
       document.write(numberOfPaths(3, 3));
 
 // This code is contributed by Potta Lokesh
   </script>
Producción

13

Complejidad de Tiempo: O(3 M*N )
Espacio Auxiliar: O(1), ya que no se ha tomado espacio extra.

Enfoque Eficiente : Dp (usando Memoización)

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
static int dp[1001][1001];
 
// Returns count of possible paths to
// reach cell at row number M and column
// number N from the topmost leftmost
// cell (cell at 1, 1)
int numberOfPaths(int M, int N)
{
 
    // If either given row number or
    // given column number is first
    if (M == 1 || N == 1)
        return 1;
     
    // If a value already present
    // in t[][], return it
    if(dp[M][N] != -1) {
        return dp[M][N];
    }
     
    // Horizontal Paths +
    // Vertical Paths +
    // Diagonal Paths
    return dp[M][N] = numberOfPaths(M - 1, N)
                    + numberOfPaths(M, N - 1)
                    + numberOfPaths(M - 1, N - 1);
}
 
// Driver Code
int main()
{
    memset(dp,-1,sizeof(dp));
    cout << numberOfPaths(3, 3);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
public class GFG {
  static int[][] dp = new int[1001][1001];
 
  // Returns count of possible paths to
  // reach cell at row number M and column
  // number N from the topmost leftmost
  // cell (cell at 1, 1)
  static int numberOfPaths(int M, int N)
  {
 
    // If either given row number or
    // given column number is first
    if (M == 1 || N == 1)
      return 1;
 
    // If a value already present
    // in t[][], return it
    if (dp[M][N] != -1) {
      return dp[M][N];
    }
 
    // Horizontal Paths +
    // Vertical Paths +
    // Diagonal Paths
    dp[M][N] = numberOfPaths(M - 1, N)
      + numberOfPaths(M, N - 1)
      + numberOfPaths(M - 1, N - 1);
    return dp[M][N];
  }
 
  // Driver Code
  public static void main(String args[])
  {
    for (int i = 0; i < 1001; i++)
      for (int j = 0; j < 1001; j++)
        dp[i][j] = -1;
    System.out.println(numberOfPaths(3, 3));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Python

# Python program for the above approach
 
# Taking the matrix as globally
dp = [[-1 for i in range(1001)] for j in range(1001)]
 
# Returns count of possible paths to
# reach cell at row number M and column
# number N from the topmost leftmost
# cell (cell at 1, 1)
def numberOfPaths(M, N):
 
    # If either given row number or
    # given column number is first
    if (M == 1 or N == 1):
        return 1
 
    # If a value already present
    # in t[][], return it
    if(dp[M][N] != -1):
        return dp[M][N]
 
    # Horizontal Paths +
    # Vertical Paths +
    # Diagonal Paths
    dp[M][N] = numberOfPaths(M - 1, N) + numberOfPaths(M,
                     N - 1) + numberOfPaths(M - 1, N - 1)
    return dp[M][N]
 
# Driver Code
print(numberOfPaths(3, 3))
 
# This code is contributed by Samim Hossain Mondal.

C#

// C# program for the above approach
using System;
class GFG {
    static int[, ] dp = new int[1001, 1001];
 
    // Returns count of possible paths to
    // reach cell at row number M and column
    // number N from the topmost leftmost
    // cell (cell at 1, 1)
    static int numberOfPaths(int M, int N)
    {
 
        // If either given row number or
        // given column number is first
        if (M == 1 || N == 1)
            return 1;
 
        // If a value already present
        // in t[][], return it
        if (dp[M, N] != -1) {
            return dp[M, N];
        }
 
        // Horizontal Paths +
        // Vertical Paths +
        // Diagonal Paths
        dp[M, N] = numberOfPaths(M - 1, N)
                   + numberOfPaths(M, N - 1)
                   + numberOfPaths(M - 1, N - 1);
        return dp[M, N];
    }
 
    // Driver Code
    public static void Main()
    {
        for (int i = 0; i < 1001; i++)
            for (int j = 0; j < 1001; j++)
                dp[i, j] = -1;
        Console.Write(numberOfPaths(3, 3));
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
        // JavaScript Program of the above approach
 
  var dp = new Array(1001);
  // Loop to create 2D array using 1D array
    for (var i = 0; i < dp.length; i++) {
        dp[i] = new Array(1001);
    }
 
  // Returns count of possible paths to
  // reach cell at row number M and column
  // number N from the topmost leftmost
  // cell (cell at 1, 1)
  function numberOfPaths(M, N)
  {
 
    // If either given row number or
    // given column number is first
    if (M == 1 || N == 1)
      return 1;
 
    // If a value already present
    // in t[][], return it
    if (dp[M][N] != -1) {
      return dp[M][N];
    }
 
    // Horizontal Paths +
    // Vertical Paths +
    // Diagonal Paths
    dp[M][N] = numberOfPaths(M - 1, N)
      + numberOfPaths(M, N - 1)
      + numberOfPaths(M - 1, N - 1);
    return dp[M][N];
  }
 
        // Driver Code
         
      for (let i = 0; i < 1001; i++){
      for (let j = 0; j < 1001; j++){
        dp[i][j] = -1;
      }}
      document.write(numberOfPaths(3, 3));
 
// This code is contributed by avijitmondal1998
    </script>
Producción

13

Complejidad de tiempo : O(M*N)

Espacio Auxiliar : O(M*N)

Publicación traducida automáticamente

Artículo escrito por prasanna1995 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 *