[LeetCode] 63. Unique Paths II

Posted on | In

Problem

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

63. Unique Paths II

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Explanation

  1. Similar to Unique Paths, but this time if obstacleGrid[row][col] is 1, then there’s 0 way to reach that point.

  2. We first check if the beginning point obstacleGrid[0][0] and the end point obstacleGrid[row-1][col-1] is 1 or not. If it’s 1, then we just return 0 as the result. Else, we need to do some checking.

  3. Initialize a two dimensional array dp[row][col] to represent the steps to reach the coordinate of row and col. We want to check the top row first. In the problem of Unique Paths, all the coordinates of top row is set to 1. But this time, we need to check if obstacle[row][col] is 1, if it’s 1, then we set dp[row][col] to 0 because there is 0 ways to reach that point. So we initialize dp[0][0] to 1, then loop through the top row as dp[0][i] = dp[0][i-1] before we assign the value of dp[0][i], check if obstacle[0][i] is 1, if it’s 1, just assign dp[0][i] as 0. Similarly, find out dp[j][0] the left most column’s value.

  4. Then, we can start to find out coordinates’ value starts from the second row, and starts from the second column, which is dp[row][col] = dp[row-1][col] + dp[row][col-1]. Of course, before we assign, check obstacle[row][col] if it is 1, if it is, then we simply assign it to 0 because there is no way to reach that coordinate.

  5. Finally, return dp[row-1][col-1].

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        int[][] dp = new int[row][col];
        if (obstacleGrid[0][0] == 1 || obstacleGrid[row-1][col-1] == 1) {
            return 0;
        }
        dp[0][0] = 1;

        for (int c = 1; c < col; c++) {
            if (obstacleGrid[0][c] == 1) {
                dp[0][c] = 0;
            } else {
                dp[0][c] = dp[0][c-1];
            }
        }
        for (int r = 1; r < row; r++) {
            if (obstacleGrid[r][0] == 1) {
                dp[r][0] = 0;
            } else {
                dp[r][0] = dp[r-1][0];
            }
        }

        for (int r = 1; r < row; r++) {
            for (int c = 1; c < col; c++) {
                if (obstacleGrid[r][c] == 1) {
                    dp[r][c] = 0;
                } else {
                    dp[r][c] = dp[r-1][c] + dp[r][c-1];
                }
            }
        }

        return dp[row-1][col-1];
    }
}