Número de formas de llegar a (M, N) en una array comenzando desde el origen sin visitar (X, Y)

Dados cuatro enteros positivos M, N, X e Y , la tarea es contar todas las formas posibles de llegar desde la parte superior izquierda (es decir, (0, 0) ) hasta la parte inferior derecha (M, N) de una array de tamaño (M+1)x(N+1) sin visitar la celda (X, Y) . Se da que desde cada celda (i, j) puede moverse solo hacia la derecha (i, j + 1) o hacia abajo (i + 1, j) .
Ejemplos:

Entrada: M = 2, N = 2, X = 1, Y = 1
Salida: 2
Explicación:
Solo hay 2 formas de llegar a (2, 2) sin visitar (1, 1) y las dos rutas son:
(0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2)
(0, 0) -> (1, 0) -> (2, 0) – > (2, 1) -> (2, 2)
Entrada: M = 5, N = 4, X = 3, Y = 2
Salida: 66
Explicación:
Hay 66 formas de llegar a (5, 4) sin visitar (3 , 2).

Enfoque:
Para resolver el problema mencionado anteriormente, la idea es restar el número de formas de llegar desde (0, 0) a (X, Y) , seguido de llegar a (M, N) desde (X, Y) visitando ( X, Y) del número total de caminos que llegan a (M, N) desde (0, 0) .
Por lo tanto,

El número de formas de llegar desde (M, N) desde el origen (0, 0) viene dado por:

$\text{Total ways from (0, 0) to (M, N)} = \binom{M + N}{M}$

El número de formas de llegar a (M, N) solo visitando (X, Y) es llegar a (X, Y) desde (0, 0) seguido de llegar a (M, N) desde (X, Y ) por:

$\text{Total ways from (0, 0) to (X, Y)} = \binom{X + Y}{X}$
$\text{Total ways from (X, Y) to (M, N)} = \binom{M + N - X - Y}{M - X}$

Por lo tanto,

$\text{Total ways from (0, 0) to (M, N) only by visting (X, Y)} = (\binom{X + Y}{X}) * (\binom{M + N - X - Y}{M - X})$

Por lo tanto, la ecuación para el número total de vías es:

$\binom{M + N}{M} - (\binom{X + Y}{X}) * (\binom{M + N - X - Y}{M - X})$

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

C++

// C++ program from the above approach
#include <bits/stdc++.h>
using namespace std;
 
int fact(int n);
 
// Function for computing nCr
int nCr(int n, int r)
{
    return fact(n)
           / (fact(r) * fact(n - r));
}
 
// Function to find factorial of a number
int fact(int n)
{
    int res = 1;
 
    for (int i = 2; i <= n; i++)
        res = res * i;
 
    return res;
}
 
// Function for counting the number
// of ways to reach (m, n) without
// visiting (x, y)
int countWays(int m, int n, int x, int y)
{
    return nCr(m + n, m)
           - nCr(x + y, x) * nCr(m + n
                                     - x - y,
                                 m - x);
}
 
// Driver Code
int main()
{
    // Given Dimensions of Matrix
    int m = 5;
    int n = 4;
 
    // Cell not to be visited
    int x = 3;
    int y = 2;
 
    // Function Call
    cout << countWays(m, n, x, y);
    return 0;
}

Java

// Java program from the above approach    
import java.util.*;    
class GFG{   
     
// Function for computing nCr    
public static int nCr(int n, int r)        
{    
    return fact(n) / (fact(r) * fact(n - r));        
}    
         
// Function to find factorial of a number    
public static int fact(int n)    
{    
    int res = 1;
     
    for(int i = 2; i <= n; i++)        
        res = res * i;        
    return res;        
}    
         
// Function for counting the number        
// of ways to reach (m, n) without        
// visiting (x, y)        
public static int countWays(int m, int n,
                            int x, int y)        
{    
    return nCr(m + n, m) -
           nCr(x + y, x) *
           nCr(m + n - x - y, m - x);        
}
 
// Driver code
public static void main(String[] args)
{    
     
    // Given Dimensions of Matrix    
    int m = 5;        
    int n = 4;        
             
    // Cell not to be visited    
    int x = 3;        
    int y = 2;        
             
    // Function Call    
    System.out.println(countWays(m, n, x, y));    
}    
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python3 program for the above approach
 
# Function for computing nCr
def nCr(n, r):
     
    return (fact(n) // (fact(r) *
                        fact(n - r)))
 
# Function to find factorial of a number
def fact(n):
     
    res = 1
    for i in range(2, n + 1):
        res = res * i
 
    return res
 
# Function for counting the number
# of ways to reach (m, n) without
# visiting (x, y)
def countWays(m, n, x, y):
     
    return (nCr(m + n, m) - nCr(x + y, x) *
            nCr(m + n - x - y, m - x))
 
# Driver Code
 
# Given dimensions of Matrix
m = 5
n = 4
 
# Cell not to be visited
x = 3
y = 2
 
# Function call
print(countWays(m, n, x, y))
 
# This code is contributed by sanjoy_62

C#

// C# program from the above approach    
using System;
 
class GFG{
     
// Function for computing nCr    
public static int nCr(int n, int r)        
{    
    return fact(n) / (fact(r) * fact(n - r));        
}    
         
// Function to find factorial of a number    
public static int fact(int n)    
{    
    int res = 1;
     
    for(int i = 2; i <= n; i++)        
        res = res * i;
         
    return res;        
}    
         
// Function for counting the number        
// of ways to reach (m, n) without        
// visiting (x, y)        
public static int countWays(int m, int n,
                            int x, int y)        
{    
    return nCr(m + n, m) -
           nCr(x + y, x) *
           nCr(m + n - x - y, m - x);        
}
 
// Driver code
public static void Main(String[] args)
{    
     
    // Given dimensions of Matrix    
    int m = 5;        
    int n = 4;        
             
    // Cell not to be visited    
    int x = 3;        
    int y = 2;        
             
    // Function call    
    Console.WriteLine(countWays(m, n, x, y));    
}    
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
 
// Javascript Program to implement
// the above approach
 
// Function for computing nCr    
function nCr(n, r)        
{    
    return fact(n) / (fact(r) * fact(n - r));        
}    
           
// Function to find factorial of a number    
function fact(n)    
{    
    let res = 1;
       
    for(let i = 2; i <= n; i++)        
        res = res * i;        
    return res;        
}    
           
// Function for counting the number        
// of ways to reach (m, n) without        
// visiting (x, y)        
function countWays(m, n, x, y)        
{    
    return nCr(m + n, m) -
           nCr(x + y, x) *
           nCr(m + n - x - y, m - x);        
}
 
// Driver Code
     
    // Given Dimensions of Matrix    
    let m = 5;        
    let n = 4;        
               
    // Cell not to be visited    
    let x = 3;        
    let y = 2;        
               
    // Function Call    
    document.write(countWays(m, n, x, y));
 
// This code is contributed by avijitmondal1998.
</script>

Producción:

Publicación traducida automáticamente

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

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta