Last Updated: 6 Jan, 2021
Distinct Paths
Moderate
Asked in companies
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
Approaches
- 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
- helper(2, 3) // rightwards
- Return 1
- helper(1, 3) // rightwards but it is blocked
- helper(2, 1) // downwards
- helper(2, 2) // rightwards
- helper(2, 3) // rightwards
- Return 1
- Return 1
- helper(2, 3) // rightwards
- Return 1
- helper(2, 2) // rightwards
- Return 2
- helper(1, 2) // rightwards
- 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.
- One observation to note here is that we can reach some cell (i, j) in two ways either from the top or from left i.e. {(i-1, j), (i, j-1)}. Hence by this recursive function, we calculate the answer for the cell at position (i, j), more than once.
- In order to stop this re-computation of the same thing, we can store the results after computing it once and use that for further calls.
- In order to store the results, we can use a N*M matrix initialized with -1 which denotes, answer for this cell is not computed till now.
- After computing the answer we just update this matrix with the result for future use.
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 …(i)
- helper(2, 3) // rightwards
- Return 1
- Return 1
- helper(2, 3) // rightwards
- Return 1
- helper(1, 3) // rightwards but it is blocked
- helper(2, 1) // downwards
- helper(2, 2) // rightwards
- Return 1 // we already computed the answer for this state at (i).
- Return 1
- helper(2, 2) // rightwards
- Return 2
- helper(1, 2) // rightwards
Similar problems