Last Updated: 12 Dec, 2020

Unique Paths II

Moderate

Asked in companies

Solve now

Problem statement

Given a ‘N’ * ’M’ maze with obstacles, count and return the number of unique paths to reach the right-bottom cell from the top-left cell. A cell in the given maze has a value '-1' if it is a blockage or dead-end, else 0. From a given cell, we are allowed to move to cells (i+1, j) and (i, j+1) only. Since the answer can be large, print it modulo 10^9 + 7.

For Example :

Consider the maze below :
0 0 0 
0 -1 0 
0 0 0

There are two ways to reach the bottom left corner - 

(1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3)
(1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)

Hence the answer for the above test case is 2.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains integers ‘N’ and ‘M’ representing the size of the input grid.

Then ‘N’ lines follow, each of which contains ‘M’ space-separated integers denoting the elements of the matrix.

Output Format :

For each test case print an integer denoting the number of ways to reach the bottom right corner from the top-left corner modulo 10^9 + 7.

Output for each test case will be printed in a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 10
1 <= N,M <= 200

Note: It is guaranteed that the top-left cell does not have an obstacle.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

We can observe that we can reach cell (i, j) only through two cells if they exist -

(i - 1, j) and (i, j - 1). Also if the cell (i, j) is blocked we can simply calculate the number of ways to reach it as zero.

So if we know the number of ways to reach cell (i - 1, j) and (i, j - 1) we can simply add these two to get the number of ways to reach cell (i, j).

Let paths(i, j) be the number of ways to reach cell (i, j).

So our recursive relation can be defined as follows:

paths(i, j) = 0 if cell is blocked or invalid.

paths(i, j) = paths(i - 1, j) + (i, j -1) otherwise.

Algorithm:

Create a recursive function paths(i, j) that will return the number of ways to reach the cell (i, j).
If the cell is invalid or blocked, return 0.
If the cell is (0, 0) return 1.
Else return (paths(i - 1, j) + paths(i, j - 1))%mod recursively.

Time Complexity:

O(2^(N + M)) Where N and M are dimensions of the input matrix.

For every cell, we are making two recursive calls with the length of the path decreasing by one. Hence the time complexity becomes O(2^(N + M)).

Solve now

02 Approach

We can observe that we are calculating the same value, again and again, using recursion.

For example paths(2, 3) and paths(3, 2) will both use paths(2, 2) which is being calculated separately twice. We can save this time by using dynamic programming and saving the results for previous paths. We memoize the results so that we can use them in the next call.

Algorithm:

Create a 2D matrix memo of the same size as the given matrix to store the value of paths(i, j) and initialize it to any other value which can’t be any answer (we initialize it with -1).
If the cell is invalid return 0.
Check if the value of memo[i][j] != -1 (we have already computed it). If yes then return it immediately.
Else calculate paths(i - 1, j) and paths(i, j - 1).
Store the result in the memo[i][j] to use it later and return it.

Solve now

03 Approach

Approach:

We can observe that we are calculating the same value, again and again, using recursion.

Algorithm:

Create a 2D matrix dp of the same size as the given matrix to store the value of paths(i, j).
Traverse through the created array row-wise and start filling the values in it.
If an obstacle is found, set the value to 0.
For the first row and column, set the value to 1 if an obstacle is not found.
Set the sum of the right and the upper values if an obstacle is not present at that corresponding position in the given matrix
Return the value of dp[n][m] finally.

Solve now