Home » Interview coding problems/challenges

Print all possible path from source to destination

Print all possible path from source to destination: The problem has been featured in interview/coding rounds of many companies such as Amazon, Citrix etc.
Submitted by Divyansh Jaipuriyar, on August 18, 2020

Problem statement

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.

Problem description

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

Input

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.

Output

Print all the possible path from the top left to bottom right of the given matrix, print each path in a new line.

Examples

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

Solution Approach

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.

Pseudo Code

Here, mat[][] is the given matrix and vis[][] is Boolean matrix.

void solve(mat[][],vis[][],x,y,n,m):
{
	if index x and y out of bound then return .
	make vis[x][y]=true
	check if x==n-1 and y==n-1
	if reached then print path.
	else
	recur for right
	recur for down
	make vis[x][y]=false again for further calls.
}	

Time complexity for the above approach is exponential.

Space complexity for the above approach is O(N*M).

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//declare solve function.
void solve(vector<vector<ll> >& v1, vector<vector<bool> >& vis, ll x, ll y, ll n, ll m)
{
    //check for index bound,if out of bound then
    //return from the function.
    if (x < 0 || x >= n || y < 0 || y >= m || vis[x][y] == true || v1[x][y] == 0)
        return;

    //make current node as visited.
    vis[x][y] = true;

    //check whether we reached
    //bottom right of matrix.
    if (x == n - 1 and y == m - 1) {

        //print path from top left
        //to bottom right.
        for (ll i = 0; i < n; i++)
            for (ll j = 0; j < m; j++) {
                //check if visited.
                if (vis[i][j])
                    cout << v1[i][j] << " ";
            }
        cout << "\n";
    }

    //recursively move for down
    solve(v1, vis, x + 1, y, n, m);

    //recursively move for right.
    solve(v1, vis, x, y + 1, n, m);

    //once completed all moves from
    //current position make current node
    //as false and further backtracking calls.
    vis[x][y] = false;
}

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of matrix: ";
        ll n, m;
        cin >> n >> m;

        vector<vector<ll> > v1(n, vector<ll>(m));
        vector<vector<bool> > vis(n, vector<bool>(m, false));

        cout << "Enter elements:\n";
        for (ll i = 0; i < n; i++)
            for (ll j = 0; j < m; j++)
                cin >> v1[i][j];
        cout << "Possible paths:\n";
        solve(v1, vis, 0, 0, n, m);
    }

    return 0;
}

Output

Enter number of test cases: 2
Enter size of matrix: 2 2
Enter elements:
4 5 
6 7
Possible paths:
4 6 7 
4 5 7 
Enter size of matrix: 3 3
Enter elements:
9 8 7 
6 5 4
3 2 1
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