LintCode (115) 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.

Have you met this question in a real interview? 

Yes

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.

Note

m and n will be at most 100.

这题没啥好讲的，handle好初始条件，其他和以前的一样

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

class Solution { public: /** * @param obstacleGrid: A list of lists of integers * @return: An integer */ int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) { // write your code here if (obstacleGrid[0][0]) return 0; int m=obstacleGrid.size(); int n=obstacleGrid[0].size(); vector<vector<int>> tbl(m, vector<int>(n, 0)); tbl[0][0]=1; for (int i=1; i<m; i++){ if (obstacleGrid[i][0] ==1){ tbl[i][0]=0; } else{ tbl[i][0]=tbl[i-1][0]; } } for (int j=1; j<n; j++){ if (obstacleGrid[0][j] ==1){ tbl[0][j]=0; } else{ tbl[0][j]=tbl[0][j-1]; } } for (int i=1; i<m; i++){ for (int j=1; j<n; j++){ if (obstacleGrid[i][j]) continue; tbl[i][j]=tbl[i-1][j]+tbl[i][j-1]; } } return tbl[m-1][n-1]; } };