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] ]
这个与前面那个题目基本上差不多，具体就是多了障碍，实际上遇到障碍的话把到该点的路径的数目置为0就可以了，其他的基本上与前面相同：
1 class Solution { 2 public: 3 int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { 4 if(obstacleGrid.size() == 0 || obstacleGrid[0].size() == 0) return 0; 5 vector<vector<int>> res(obstacleGrid.size(), vector<int>(obstacleGrid[0].size(), 0)); 6 int maxHor = obstacleGrid.size(); 7 int maxVer = obstacleGrid[0].size(); 8 res[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1; 9 for(int i = 1; i < maxHor; ++i){ 10 res[i][0] = obstacleGrid[i][0] == 1 ? 0 : res[i - 1][0]; 11 } 12 for(int j = 1; j < maxVer; ++j){ 13 res[0][j] = obstacleGrid[0][j] == 1 ? 0 : res[0][j - 1]; 14 } 15 for(int i = 1; i < maxHor; ++i){ 16 for(int j = 1; j < maxVer; ++j){ 17 res[i][j] = obstacleGrid[i][j] == 1 ? 0 : res[i - 1][j] + res[i][j - 1]; 18 } 19 } 20 return res[maxHor - 1][maxVer - 1]; 21 } 22 };
LeetCode OJ：Unique Paths II（唯一路径II）
原文：http://www.cnblogs.com/-wang-cheng/p/4901486.html