Problem Statement
Unique Paths II
You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m-1][n-1]). The robot can only move either down or right at any point in time.
An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 10^9.
Examples
Example 1:
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:
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
Explanation: There is one obstacle in the top right corner.
There is only one way to reach the bottom-right corner:
Down -> Right
Constraints
- m == obstacleGrid.length
- n == obstacleGrid[i].length
- 1 <= m, n <= 100
- obstacleGrid[i][j] is 0 or 1
Problem Breakdown
To solve this problem, we need to:
- This problem is an extension of the 'Unique Paths' problem, with the addition of obstacles.
- We can still use dynamic programming, but we need to handle the obstacles differently.
- If a cell contains an obstacle, the number of ways to reach that cell is 0.
- For non-obstacle cells, the recurrence relation is the same as in 'Unique Paths': dp[i][j] = dp[i-1][j] + dp[i][j-1].
- We need to check if the starting cell or the destination cell contains an obstacle. If either does, the answer is 0.
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
Unique Paths II
You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m-1][n-1]). The robot can only move either down or right at any point in time.
An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 10^9.
Examples
Example 1:
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:
There is one obstacle in the top right corner. There is only one way to reach the bottom-right corner: Down -> Right
Problem Breakdown
Constraints:
- m == obstacleGrid.length
- n == obstacleGrid[i].length
- 1 <= m, n <= 100
- obstacleGrid[i][j] is 0 or 1
Key Insights:
This problem is an extension of the 'Unique Paths' problem, with the addition of obstacles.
We can still use dynamic programming, but we need to handle the obstacles differently.
If a cell contains an obstacle, the number of ways to reach that cell is 0.
For non-obstacle cells, the recurrence relation is the same as in 'Unique Paths': dp[i][j] = dp[i-1][j] + dp[i][j-1].
We need to check if the starting cell or the destination cell contains an obstacle. If either does, the answer is 0.
Real-World Application
This problem has several practical applications:
Robot Path Planning with Obstacles
Planning optimal paths for robots in environments with obstacles, such as warehouses or factories.
Network Routing with Blocked Paths
Calculating the number of possible routes in network topologies with restricted movement directions and blocked paths.
City Navigation with Road Closures
Determining the number of possible routes in a city with a grid-like street layout where some streets are closed or blocked.