Unique Paths II

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.

Note

m and n will be at most 100.

Example

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.

 
class Solution {
public:
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */ 
     int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
         int m = obstacleGrid.size();
         if (m == 0) return 0;
         int n = obstacleGrid[0].size();
         if (n ==0) return 0;
         vector<vector<int>> map(m, vector<int>(n, 0));
         if (obstacleGrid[m-1][n-1]== 1 || obstacleGrid[0][0]) return 0;
              
         for(int i = m-1; i >=0; i--)
          for(int j = n-1; j >=0; j--) 
              if (i== m-1 && j == n-1) 
                 map[i][j] = 1;
              else if (i == m-1) // special on last row
                 map[i][j] =  (obstacleGrid[i][j] == 1)? 0:map[i][j+1];
              else if (j == n-1) // special on last column
                 map[i][j] =  (obstacleGrid[i][j] == 1)? 0:map[i+1][j];
              else
                 map[i][j] = (obstacleGrid[i][j] == 1)? 0:map[i+1][j]+ map[i][j+1];
        
         return map[0][0];
    }
};

 
class Solution {
public:
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */ 
     int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
         int m = obstacleGrid.size();
         if (m == 0) return 0;
         int n = obstacleGrid[0].size();
         if (n ==0) return 0;
         
         if (obstacleGrid[m-1][n-1]== 1 || obstacleGrid[0][0]) return 0;
         vector<int> map(n, 1);
         
              
         for(int i = m-1; i >=0; i--)
          for(int j = n-1; j >=0; j--) 
              if (i== m-1 && j == n-1) 
                 map[j] = 1;
              else if (i == m-1) // special on last row
                 map[j] =  (obstacleGrid[i][j] == 1)? 0:map[j+1];
              else if (j == n-1) // special on last column
                 map[j] =  (obstacleGrid[i][j] == 1)? 0:map[j];
              else
                 map[j] = (obstacleGrid[i][j] == 1)? 0:map[j]+ map[j+1];
        
         return map[0];
    }
};