Home » Interview coding problems/challenges

Count Unique Path

You are given a matrix of size N*M, you start from first cell and you need to reach bottom right cell. You need to print count of all the unique path that are possible.
Submitted by Divyansh Jaipuriyar, on September 03, 2020

Problem statement

You are given a matrix of size N*M, you start from first cell and you need to reach bottom right cell. You need to print count of all the unique path that are possible. Each cell of the matrix is either 0 which is blocked cell or 1 unblocked cell. You can move in all four direction from (i,j) to (i+1,j),(i-1,j),(i,j+1) and (i,j-1).

Problem description

The problem needs you to find all the different paths that are possible from (0,0) to (N-1,M-1) index location in the matrix, the matrix is filled with 0 or 1 ,1 means that you can travel in that cell and 0 means it is blocked hence you only move in cells which have 1 in it, along with that you can only move in all four direction from current cell if the visiting cell is under correct boundary index range.

Input

The first line of the input is the T number of test cases, each test case consists of N and M the size of matrix and each of the following N lines consist of M number of elements either 0 or 1.

Output

Print the number of unique paths which are possible from source to destination.

Examples

Input:
T=1
N=4,M=4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Output:
184

Input:
T=1
N=4,M=4
1 1 1 1
1 1 0 1
0 1 0 1
1 1 1 1

Output:
4

Solution Approach

To solve this problem, we need to use backtracking we need to find that path that will make us move from source to destination. In order to know which are the cells that are involved in the formation of the path, we need to know either it lies in the path or not, and explore the rest of the four-cell which are connected to it. If the four other cells that are connected to the cell are completely exhausted without reaching the final cell then the current cell is not involved in the path since the other cell could only be reached through the current cell, so we backtrack and consider other possibilities.

In order to avoid cycles in the path, we need to use some boolean matrix vis which will tell us whether we have visited the cell or not. Before moving to any cell we will first check whether it has already visited or not.

We will also create a boolean function issafe which will tell us whether the cell that we are going to visit has its index range within the boundary range or not.

We will follow the given steps:

1. Start from the source cell(0,0) and check if this is the desired cell or not.
2. Mark this cell as visited and check for all the four cells connected to it.
3. If any of the cells are already visited then move to the next cell of the given four directions.
4. If the given parent cell of four directions fails to reach to final destination then make that cell as unmarked.
5. After unmarking that cell backtrack.
6. Repeat the above steps until your recursion function terminates.

Time complexity for the above approach in the worst case is exponential.

Space complexity for the above approach in the worst case is: (N*M) that is the size of the matrix.

C++ Implementation

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

typedef long long ll;

//boolean visited array
bool vis[1003][1003];

//matrix to store path values.
ll mat[1003][1003];

//boolean safe function for checking
//index bound range.
bool issafe(ll x, ll y, ll n, ll m)
{
    //if inside index range then return true.
    if (x >= 0 and x < n and y >= 0 and y < m)
        return true;
    else //otherwise return false.
    {
        return false;
    }
}

//void solve function to find the total
//count of the unique path from source to dest.
void solve(ll x, ll y, ll& cnt, ll n, ll m)
{
    //if reached at destination.
    if (x == n - 1 and y == m - 1) {
        //increment count.
        cnt++;
        return;
    }
    //mark visited
    vis[x][y] = true;

    //check for other four direction.
    if (issafe(x, y, n, m) and mat[x][y]) {
        //if move downward  direction.
        if (issafe(x + 1, y, n, m) and vis[x + 1][y] == false) {
            solve(x + 1, y, cnt, n, m);
        }
        //if move in upward directon.
        if (issafe(x - 1, y, n, m) and vis[x - 1][y] == false)
            solve(x - 1, y, cnt, n, m);

        //if move in rightward direction.
        if (issafe(x, y + 1, n, m) and vis[x][y + 1] == false) {
            solve(x, y + 1, cnt, n, m);
        }
        //if move in leftward direction.
        if (issafe(x, y - 1, n, m) and vis[x][y - 1] == false)
            solve(x, y - 1, cnt, n, m);
    }
    //unmark the current cell as it failed to
    //be in the path from source to destination
    //and for backtracking.
    vis[x][y] = false;
}

int main()
{
    ll t;
 
    cout << "Enter number of test cases: ";
    cin >> t;
 
    while (t--) {
        memset(vis, false, sizeof(vis));
 
        ll n, m;
        cout << "Enter size of matrix N and M: ";
        cin >> n >> m;
 
        cout << "Enter elements:\n";
        for (ll i = 0; i < n; i++)
            for (ll j = 0; j < m; j++)
                cin >> mat[i][j];
 
        ll cnt = 0;
 
        solve(0, 0, cnt, n, m);
 
        cout << "Total unique paths: ";
        cout << cnt << "\n";
    }
    
    return 0;
}

Output

Enter number of test cases: 3
Enter size of matrix N and M: 4 4
Enter elements:
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
Total unique paths: 184
Enter size of matrix N and M: 4 4
Enter elements:
1 1 1 1
1 1 0 1
0 1 0 1
1 1 1 1
Total unique paths: 4
Enter size of matrix N and M: 2 2
Enter elements:
1 0
0 1
Total unique paths: 0