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.
Solutions:
class Solution { public: int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) { if(obstacleGrid.size() < 1) return 0; int m = obstacleGrid.size(), n = obstacleGrid[0].size(); int **paths = new int*[m]; for(int i = 0;i < m;i++) { paths[i] = new int[n]; memset(paths[i], 0, n * sizeof(int)); } for(int i = 0;i < m;i++) { for(int j = 0;j < n;j++) { if(i == 0 && j == 0) paths[i][j] = 1 - obstacleGrid[i][j]; else if(obstacleGrid[i][j] == 1) paths[i][j] = 0; else { if(i - 1 < 0) { if(j - 1 < 0) paths[i][j] = 0; else paths[i][j] = paths[i][j - 1]; } else { if(j - 1 < 0) paths[i][j] = paths[i - 1][j]; else paths[i][j] = paths[i - 1][j] + paths[i][j - 1]; } } } } return paths[m - 1][n - 1]; } };
[LeetCode] Unique Paths II,布布扣,bubuko.com
原文：http://www.cnblogs.com/changchengxiao/p/3592631.html