Unique Paths II Problem


Description

LeetCode Problem 63.

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?

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

Example 1:

1
2
3
4
5
6
Input: obstacleGrid = [[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

Example 2:

1
2
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

Constraints:

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] is 0 or 1.


Sample C++ Code

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
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid.size() == 0)
            return 0;
        
        int r = obstacleGrid.size(), c = obstacleGrid[0].size();
        vector<vector<int>> dp(r, vector<int>(c, 0));
        for (int i = 0; i < r; i ++) {
            for (int j = 0; j < c; j ++) {
                if (obstacleGrid[i][j] == 1)
                    dp[i][j] = 0;
                else {
                    if ((i == 0) && (j == 0)) {
                        dp[i][j] = 1;
                    } else if (i == 0) {
                        dp[i][j] = dp[i][j-1];
                    } else if (j == 0) {
                        dp[i][j] = dp[i-1][j];
                    } else {
                        dp[i][j] = dp[i-1][j] + dp[i][j-1];
                    }
                }
            }
        }
        return dp[r-1][c-1];
    }
};




Related Posts

Maximum Product Subarray Problem

LeetCode 152. Given an integer array nums, find a contiguous...

House Robber Problem

LeetCode 198. You are a professional robber planning to rob...

Dungeon Game Problem

LeetCode 174. The demons had captured the princess and imprisoned...

Best Time To Buy And Sell Stock IV Problem

LeetCode 188. You are given an integer array prices where...

Palindrome Partitioning II Problem

LeetCode 132. Given a string s, partition s such that...

Triangle Problem

LeetCode 120. Given a triangle array, return the minimum path...