Follow up for "Unique Paths":
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
.
Solution:
int help(int m, int n, vector<vector<int> >& obstacleGrid, vector<vector<int> >& result)
{
if(result[m][n]!=-1)
{
return result[m][n];
}
result[m][n] = 0;
if(obstacleGrid[m-1][n-1]==1)
{
return 0;
}
if(m>1)
result[m][n] += help(m-1,n,obstacleGrid, result);
if(n>1)
result[m][n] += help(m,n-1,obstacleGrid ,result);
return result[m][n];
}
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
if(obstacleGrid.size()==0)
return 0;
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int> > result(m+1, vector<int>(n+1, -1));
if(obstacleGrid[0][0]==0)
{
result[1][1] = 1;
}
else
result[1][1] = 0;
help(m, n, obstacleGrid, result);
return result[m][n];
}
No comments:
Post a Comment