Print all possible path from source to destination
You are given a matrix of the size of N*M, you need to print all the paths from top left to the bottom right of the given matrix. You can only move in right and down direction.
The problem wants you to find all the possible path from source(0,0) to destination(N-1,M-1) such that the path you follow must be either right or down from the previous point. i.e. (i,j)->(i+1,j) and (i,j)->(i,j+1).
The first line of the input is the T number of test cases, each test case consists of two numbers N and M denoting the size of the matrix, following each of the N lines consists of M elements.
Print all the possible path from the top left to bottom right of the given matrix, print each path in a new line.
Input: T=1 N=3,M=3 9 8 7 6 5 4 3 2 1 Output: Possible paths: 9 6 3 2 1 9 6 5 2 1 9 6 5 4 1 9 8 5 2 1 9 8 5 4 1 9 8 7 4 1
The problem can be solved with the help of the backtracking concept. We will recursively check for the right movement and down movement from the current position each time, once we reached destination then we will print the path.
In order to check for each point in the matrix, we will use a visited array, if it is true then it means we have already visited or if it is false then we haven't visited it, if the given cell is already visited then we will simply skip it from the path and recur for another path.
For each position in the given matrix, we have two possibilities either it will be in the path or it will not be in the path. Once we reached the bottom right point then we will not return from it, we will print the path that has been used to reach the bottom end and again we check if is it possible to reach the bottom right from right of current position or from down of current position, if not then we will make the visited array false.
Time complexity for the above approach is exponential.
Space complexity for the above approach is O(N*M).
Output:need an explanation for this answer? contact us directly to get an explanation for this answer