Distinct Paths

Moderate
0/80
Average time to solve is 20m
4 upvotes
Asked in companies
OlaFacebook

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
2 2
0 0
0 0
Sample Output 1 :
2
Explanation of sample input 1 :
There are 2 possible paths to go from (1,1) to (N, M) which is (2,2).
ie. {(1, 1), (1, 2), (2, 2)} and {(1, 1), (2, 1), (2, 2)}.
Sample Input 2 :
1
2 3
0 0 1
0 0 0
Sample Output 2 :
2
Explanation of sample input 2 :
There are 2 possible paths to go from (1, 1) to (N, M) which is (2, 3).
ie. {(1, 1), (1, 2), (2, 2), (2, 3)} and {(1, 1), (2, 1), (2, 2), (2, 3)}.
Hint

Try all possible paths and increment the counter after reaching the bottom right corner of the matrix.

Approaches (2)
Brute Solution
  • 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
Time Complexity

O(2^(N+M)), where N and M are the given number of rows and columns of the matrix.

 

As there are two options from each cell, either to move towards the right or going downwards. Also, the maximum number of cells we go through in our path will be N+M-1.

Space Complexity

O(1).

 

As we are using constant extra memory.

Code Solution
(100% EXP penalty)
Distinct Paths
Full screen
Console