Leetcode: UniquePath II

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と基本的に同じで、格子に障害物を加えただけです.基本的な考え方は深捜し+メモ
でもなぜかタイムアウト..基本的には答えと同じで、後で分析します.

 1 int pathrec[102][102]={0};
 2 class Solution {
 3 public:
 4 
 5     int findpath(vector<vector<int> >& grid, int m, int n,int x,int y)
 6     {
 7         if(grid[m][n]==1)
 8             return 0;
 9         
10         if(pathrec[m][n]!=0)
11             return pathrec[m][n];
12         int pathnum = 0;
13         if(m==x-1 && n==y-1)
14         {
15             pathrec[m][n] = 1;
16             return 1;
17         }
18         
19         if(m+1<x) pathnum+= findpath(grid,m+1,n,x,y);
20         if(n+1<y) pathnum+= findpath(grid,m,n+1,x,y);
21         pathrec[m][n] = pathnum;
22         return pathnum;
23     }
24     int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
25         if(obstacleGrid.empty() || obstacleGrid[0].empty()) return 0;
26         int x = obstacleGrid.size(); int y= obstacleGrid[0].size();
27         memset(pathrec,0,sizeof(pathrec));
28         int pathnum = findpath(obstacleGrid,0,0,x,y);
29         return pathnum;
30     }
31 };