Count of all unique paths from given source to destination in a Matrix

0 0 3 minutes read

Given a 2D matrix of size n*m, a source ‘s’ and a destination ‘d’, print the count of all unique paths from given ‘s’ to ‘d’. From each cell, you can either move only to the right or down.

Examples:

Input: arr[][] = { {1, 2, 3}, {4, 5, 6} }, s = {0, 0}, d = {1, 2}
Output: 3
Explanation: All possible paths from source to destination are:

1 -> 4 -> 5 -> 6

1 -> 2 -> 5 -> 6

1 -> 2 -> 3 -> 6

Input: arr[][] = { {1, 2}, {3, 4} }, s = {0, 1}, d = {1, 1}
Output: 1

Approach: Use recursion to move right first & then down from each cell in the path of the matrix, starting from the source. If the destination is reached, increment the count of possible paths.

Below is the implementation of the above approach:

C++

// 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

// 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.

Python3

# 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#

// 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.

Javascript

<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>

Output

Time Complexity: O(n+m)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!