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 3×3 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.
分析：这道题是上一道题的升级版~加了障碍物~加不加障碍物差别就在于，当当前地域有障碍物的时候，a[i][j] = 0，其余的不变：
0.a[0][0] = 1; 1.对于i==0的时候，为最上面一排，当前方格只能由左边方格来，所以a[i][j] = a[i][j-1]; 2.对于j==0的时候，为最左边一排，当前方格只能由上边方格来，所以a[i][j] = a[i-1][j]; 3.其余情况，当前方格能由左边和上边两个方向过来，所以a[i][j] = a[i-1][j] + a[i][j-1]; 最后直到一直递推输出到终点(m-1, n-1)的时候return a[m-1][n-1];
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); int a[100][100]; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(obstacleGrid[i][j] == 1) { a[i][j] = 0; } else if(i == 0 && j == 0) { a[i][j] = 1; } else if(i == 0) { a[i][j] = a[i][j-1]; } else if(j == 0) { a[i][j] = a[i-1][j]; } else { a[i][j] = a[i-1][j] + a[i][j-1]; } } } return a[m-1][n-1]; } }; |
❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼
❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼
❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版
