Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as
1
and 0
respectively in the grid.For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[ [0,0,0], [0,1,0], [0,0,0] ]The total number of unique paths is
2
.Note: m and n will be at most 100.
Solution: dynamic programming; similar to the Unique Path I; the only thing you need to take care of is "obstacle" (Lines 11-14).
class Solution { public: int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) { // Note: The Solution object is instantiated only once and is reused by each test case. if(obstacleGrid.empty() || obstacleGrid[0].empty()) return 0; int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); vector<vector<int> > paths(m, vector<int>(n, 0)); for(int i=m-1; i>=0; i--){ for(int j=n-1; j>=0; j--){ if(obstacleGrid[i][j]==1){ paths[i][j] = 0; continue; } if(i==m-1){ paths[i][j] = (j==n-1?1:paths[i][j+1]); } else{ paths[i][j] = paths[i+1][j] + (j==n-1?0:paths[i][j+1]); } } } return paths[0][0]; } };
No comments:
Post a Comment