Distinct Paths

Posted: 6 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given a Binary Matrix A of dimensions N*M. You are standing at the top left corner of the matrix and want to reach the bottom right corner of the matrix. You are only allowed to move rightwards or downwards. If the value of any cell is ‘1’, then you cannot move to this cell(or in other words the move to this cell is forbidden), whereas if the cell value is ‘0’, then you can freely move to this cell(or in other words the move to this cell is permissible).

You have to count the number of ways to reach the bottom right corner of the matrix. As the number of ways can be large in some cases, hence find it modulo 10^9+7.

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[1][1] = 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
Try Problem