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.

Note: m and n will be at most 100.

1 class Solution { 2 public: 3     int uniquePathsWithObstacles(vector
      
       
        >& obstacleGrid) { 4         int ans=0; 5         int m=obstacleGrid.size(); 6         if(!m) 7             return ans; 8         int n=obstacleGrid[0].size(); 9         10         vector
        
          jlist(n,0);11         for(int i=n-1;i>=0;i--)12         {13             if(obstacleGrid[m-1][i]==1)14                 break;15             else16                 jlist[i]=1;17         }18         19         for(int i=m-2;i>=0;i--)20         {21             for(int j=n-1;j>=0;j--)22             {23                 if(j==n-1)24                 {25                     if(obstacleGrid[i][j]==1)26                         jlist[j]=0;27                 }28                 else29                 {30                 31                 if(obstacleGrid[i][j]==1)32                     jlist[j]=0;33                 else34                     jlist[j]+=jlist[j+1];35                     36                 }37                 38                 39             }40         }41         return jlist[0];42     }43 };