Description:
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.
分析：这道题目跟之前的UniquePath基本都是一样的，只是在格子中加了障碍物。基本思路是深搜+备忘录
但是不知道为什么会超时。。基本就跟答案一样，以后分析
int pathrec[][]={};
class Solution {
public:
int findpath(vector<vector<int> >& grid, int m, int n,int x,int y)
{
if(grid[m][n]==)
return ;
if(pathrec[m][n]!=)
return pathrec[m][n];
int pathnum = ;
if(m==x- && n==y-)
{
pathrec[m][n] = ;
return ;
}
if(m+<x) pathnum+= findpath(grid,m+,n,x,y);
if(n+<y) pathnum+= findpath(grid,m,n+,x,y);
pathrec[m][n] = pathnum;
return pathnum;
}
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
if(obstacleGrid.empty() || obstacleGrid[].empty()) return ;
int x = obstacleGrid.size(); int y= obstacleGrid[].size();
memset(pathrec,,sizeof(pathrec));
int pathnum = findpath(obstacleGrid,,,x,y);
return pathnum;
}
};