A robot is located at the top-left corner of a n x m grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any moment of time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
Now consider obstacles are placed in some of the grid's cells. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
Note: n and m will be at most 100.
It is guaranteed that the answer can be represented as a 32-bit integer.
Example 1:
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
The core challenge of this problem is to find the number of unique paths from the top-left corner to the bottom-right corner of a grid, considering that some cells may contain obstacles. The robot can only move right or down, which limits the possible paths.
This problem is significant in various applications, such as pathfinding in robotics, game development, and network routing. A common pitfall is not accounting for obstacles correctly, which can lead to incorrect path counts.
To solve this problem, we can use dynamic programming. The idea is to create a 2D array dp where dp[i][j] represents the number of unique paths to reach cell (i, j).
1. **Naive Solution**: A naive approach would involve recursively exploring all possible paths, but this would be highly inefficient due to overlapping subproblems and exponential time complexity.
2. **Optimized Solution**: Using dynamic programming, we can build the solution iteratively. We initialize the starting point and then fill the dp array based on the possible moves (right and down), while considering obstacles.
1. Initialize a 2D array dp with the same dimensions as the grid.
2. Set dp[0][0] to 1 if the starting cell is not an obstacle.
3. Iterate through the grid, and for each cell, update the dp value based on the values from the cell above and the cell to the left, if they are not obstacles.
4. The value at dp[n-1][m-1] will be the number of unique paths to the bottom-right corner.
public class UniquePaths {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.length;
int m = obstacleGrid[0].length;
// If the starting cell has an obstacle, return 0
if (obstacleGrid[0][0] == 1) {
return 0;
}
// Initialize the dp array
int[][] dp = new int[n][m];
dp[0][0] = 1;
// Fill the first column
for (int i = 1; i < n; i++) {
dp[i][0] = (obstacleGrid[i][0] == 1) ? 0 : dp[i - 1][0];
}
// Fill the first row
for (int j = 1; j < m; j++) {
dp[0][j] = (obstacleGrid[0][j] == 1) ? 0 : dp[0][j - 1];
}
// Fill the rest of the dp array
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[n - 1][m - 1];
}
}
The time complexity of this approach is O(n * m) because we iterate through each cell of the grid once. The space complexity is also O(n * m) due to the additional 2D array used for dynamic programming.
1. The starting cell or the ending cell is an obstacle.
2. The grid is entirely free of obstacles.
3. The grid is filled with obstacles except for the starting and ending cells.
To handle these edge cases, we ensure that the initial and final cells are checked for obstacles and handle them accordingly.
To test the solution comprehensively, consider the following test cases:
Using a testing framework like JUnit can help automate and validate these test cases effectively.
1. Break down the problem into smaller subproblems and solve them iteratively.
2. Use dynamic programming to store intermediate results and avoid redundant calculations.
3. Practice similar problems to improve your understanding of dynamic programming and pathfinding algorithms.
Understanding and solving the "Unique Paths" problem with obstacles is a valuable exercise in dynamic programming and pathfinding. By breaking down the problem and using an optimized approach, we can efficiently find the number of unique paths in a grid with obstacles.
Practice and exploration of similar problems will further enhance your problem-solving skills and algorithmic thinking.