Recuento de todas las rutas únicas desde el origen dado hasta el destino en una array

Dada una array 2D de tamaño n*m , un origen ‘ s ‘ y un destino ‘ d ‘, imprima el recuento de todas las rutas únicas desde ‘ s ‘ dado a ‘ d ‘. Desde cada celda, puede moverse solo hacia la derecha o hacia abajo .

Ejemplos :

Entrada : arr[][] = { {1, 2, 3}, {4, 5, 6} }, s = {0, 0}, d = {1, 2}
Salida : 3
Explicación : Todas las rutas posibles desde origen a destino son:

• 1 -> 4 -> 5 -> 6
• 1 -> 2 -> 5 -> 6
• 1 -> 2 -> 3 -> 6

Entrada : arr[][] = { {1, 2}, {3, 4} }, s = {0, 1}, d = {1, 1}
Salida : 1

Enfoque : use la recursividad para moverse primero hacia la derecha y luego hacia abajo desde cada celda en la ruta de la array, comenzando desde la fuente . Si se alcanza el destino , incremente el conteo de caminos posibles .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the
// count of all possible paths
int countPaths(int i, int j, int count,
               int p, int q)
{
    // Destination is reached
    if (i == p || j == q) {
        count++;
        return count;
    }
 
    // Move right
    count = countPaths(i, j + 1,
                       count, p, q);
 
    // Move down
    count = countPaths(i + 1, j,
                       count, p, q);
    return count;
}
 
// Driver program to test above functions
int main()
{
    vector<vector<int> > mat = { { 1, 2, 3 },
                                 { 4, 5, 6 } };
    vector<int> s = { 0, 0 };
    vector<int> d = { 1, 2 };
    cout << countPaths(s[0], s[1], 0,
                       d[0], d[1]);
    return 0;
}

// Java program for the above approach
class GFG {
 
    // Function to find the
    // count of all possible paths
    static int countPaths(int i, int j, int count,
            int p, int q) {
       
        // Destination is reached
        if (i == p || j == q) {
            count++;
            return count;
        }
 
        // Move right
        count = countPaths(i, j + 1,
                count, p, q);
 
        // Move down
        count = countPaths(i + 1, j,
                count, p, q);
        return count;
    }
 
    // Driver program to test above functions
    public static void main(String args[]) {
        int[] s = { 0, 0 };
        int[] d = { 1, 2 };
        System.out.println(countPaths(s[0], s[1], 0, d[0], d[1]));
    }
}
 
// This code is contributed by gfgking.

# python program for the above approach
 
# Function to find the
# count of all possible paths
def countPaths(i, j, count, p, q):
 
    # Destination is reached
    if (i == p or j == q):
        count += 1
        return count
 
    # Move right
    count = countPaths(i, j + 1, count, p, q)
 
    # Move down
    count = countPaths(i + 1, j, count, p, q)
    return count
 
# Driver program to test above functions
if __name__ == "__main__":
 
    mat = [[1, 2, 3],
           [4, 5, 6]]
    s = [0, 0]
    d = [1, 2]
    print(countPaths(s[0], s[1], 0, d[0], d[1]))
 
    # This code is contributed by rakeshsahni

// C# program for the above approach
 
using System;
class GFG {
 
    // Function to find the
    // count of all possible paths
    static int countPaths(int i, int j, int count, int p, int q) {
       
        // Destination is reached
        if (i == p || j == q) {
            count++;
            return count;
        }
 
        // Move right
        count = countPaths(i, j + 1,
                count, p, q);
 
        // Move down
        count = countPaths(i + 1, j,
                count, p, q);
        return count;
    }
 
    // Driver program to test above functions
    public static void Main() {
        int[] s = { 0, 0 };
        int[] d = { 1, 2 };
        Console.Write(countPaths(s[0], s[1], 0, d[0], d[1]));
    }
}
 
// This code is contributed by gfgking.

<script>
       // JavaScript code for the above approach
 
       // Function to find the
       // count of all possible paths
       function countPaths(i, j, count,
           p, q)
       {
        
           // Destination is reached
           if (i == p || j == q) {
               count++;
               return count;
           }
 
           // Move right
           count = countPaths(i, j + 1,
               count, p, q);
 
           // Move down
           count = countPaths(i + 1, j,
               count, p, q);
           return count;
       }
 
       // Driver program to test above functions
       let mat = [[1, 2, 3],
                   [4, 5, 6]];
       let s = [0, 0];
       let d = [1, 2];
       document.write(countPaths(s[0], s[1], 0,
           d[0], d[1]));
 
 // This code is contributed by Potta Lokesh
   </script>

3

Tiempo Complejidad : O(n+m)
Espacio Auxiliar : O(1)