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

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:

Time complexityfor the above approach in the worst case is.exponentialSpace complexityfor the above approach in the worst case is:that is the size of the matrix.(N*M)C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: