# Distinct Paths

Posted: 6 Jan, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### Note :

``````1. It is impossible to move outside the matrix.
2. The starting point which is the top left corner of the matrix and the destination point which is the bottom right corner of the matrix is always empty, ie  A = A[N][M] = 0 (taking 1 based indexing).
3. By rightwards move it means you can go to A[x][y+1] from some cell A[x][y], if A[x][y+1] exists and moving to A[x][y+1] is not forbidden.
4. By downwards move it means you can go to A[x+1][y] from some cell A[x][y], if A[x+1][y] exists and moving to A[x+1][y] is not forbidden.
``````
##### Input Format :
``````The first line of input contains an integer T, denoting the number of test cases.

The first line of each test case consists of two space-separated integers N and M denoting the number of rows and number of columns of the Binary Matrix A respectively.

The following N lines contain M space-separated booleans ( 0’s or 1’s) denoting the permissible and forbidden positions respectively, as described in the problem statement.
``````
##### Output Format :
``````For each test case, print the number of ways to go from the top left corner to the bottom right corner of the given matrix.
``````
##### Note :
``````You don't have to print anything, it has already been taken care of. Just Implement the given function.
``````
##### Constraints :
``````1 <= T <= 10
1 <= N, M <= 1000
0 <= A[i][j] <= 1, for each cell position (i, j)

The summation of N*M for all test cases won’t exceed 10^6.

Time Limit: 1 sec
`````` Approach 1
• Make a recursive function that will return the number of ways to reach the bottom right corner of the matrix from some position (i, j).
• The base Condition for this function will be when we reach the bottom right corner. We return 1 in this condition as we get one possible path.
• In the case other than the base case we try to find the total number of ways by moving rightwards and downwards both as follows:
• For finding a path possible by moving towards rightwards, we first check if the right cell which is (i, j+1) exists for some cell at (i, j) if it exists then we check if it is not blocked. If both conditions are satisfied then we call the same recursive function for (i, j+1) and add its result into our answer.
• For finding a path possible by moving towards downwards, we first check if the down cell which is (i+1, j) exists for some cell at (i, j) if it exists then we check if it is not blocked. If both conditions are satisfied then we call the same recursive function for (i+1, j) and add its result into our answer.
• We just need to call this function for (1, 1), which is the top left corner of the matrix.

Eg. For following input binary matrix:

This algorithm works like this.

• helper(1, 1)
• helper(1, 2) // rightwards
• helper(1, 3) // rightwards but it is blocked
• Return 0
• helper(2, 2) // downwards
• helper(2, 3) // rightwards
• Return 1
• Return 1
• Return 1
• helper(2, 1) // downwards
• helper(2, 2) // rightwards
• helper(2, 3) // rightwards
• Return 1
• Return 1
• Return 1
• Return 2