Introduction
This blog will discuss the approach to return the count of all unique paths from a given source to destination in a Matrix. Before jumping on the approach to return the count of all unique paths from a given source to destination in a Matrix, let’s first understand what is the problem,
Must recommended topic about, kth largest element in an array, and Euclid GCD Algorithm
Problem Statement
In this problem, we’ll be provided with the source and destination in the 2D matrix, and we need to return the total number of the possible unique path to reach the destination by moving in the down or right direction only.
Sample Example
Input:
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Source: {0 , 0}
Destination: {2, 2}
Output:
6
Explanation:
All unique paths possible are :-
1 -> 2 -> 3 -> 6 -> 9
1 -> 2 -> 5 -> 6 -> 9
1 -> 2 -> 5 -> 8 -> 9
1 -> 4 -> 5 -> 6 -> 9
1 -> 4 -> 5 -> 8 -> 9
1 -> 4 -> 7 -> 8 -> 9
Approach
This approach considers recursion which is used to move in the allowed direction ie. Right and down from each cell. In this way, when we reach the destination, we need to increment the count of possible unique paths.
Steps of Algorithm
Step 1. Call a ‘getResult’ function, which takes 5 parameters, 4 integer parameters ie. the x and y coordinates of the source, and destination cell and the fifth is the count integer variable to store the count of possible unique paths.
Step 2. In this function, check for the base case, in which if the x1, y1 is equal to x2, y2, which means we reached the destination, then increment the count variable and return count.
Step 3. If the base is not triggered then, make a recursive call for right movement by passing the y1 as y1 + 1 and assigning the returned integral value to count.
Step 4. Now again make a recursive call for left movement by passing the x1 as x1 + 1 and assigning the returned integral value to count.
Step 5. Return the count variable.