首页 > 代码库 > 【LeetCode】Unique Paths II
【LeetCode】Unique Paths II
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]; } }};
【LeetCode】Unique Paths II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。