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.
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.
与上题差别不大，只需要判断有障碍置零即可。
对于首行首列，第一个障碍及之后的路径数均为0
class Solution { public: int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) { if(obstacleGrid.empty()) return 0; else if(obstacleGrid[0].empty()) return 0; else {//m>=1, n>=1 int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); vector<vector<int> > count(m, vector<int>(n, 0)); for(int i = 0; i < m; i ++) { if(obstacleGrid[i][0] == 0) count[i][0] = 1; else break; } for(int j = 0; j < n; j ++) { if(obstacleGrid[0][j] == 0) count[0][j] = 1; else break; } for(int i = 1; i < m; i ++) { for(int j = 1; j < n; j ++) { if(obstacleGrid[i][j] == 1) count[i][j] = 0; else count[i][j] = count[i-1][j]+count[i][j-1]; } } return count[m-1][n-1]; } } };
原文：http://www.cnblogs.com/ganganloveu/p/4155248.html