首页 > 代码库 > [leetcode]Unique Paths II
[leetcode]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
and0
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.
基本思路:
此题是前篇Unique Paths 的变形。加入了障碍格子。但是思路与前篇基本一致,只是在前篇的基础上考虑了障碍格子。变化的地方有两个:
- 初始化第一行第一列时考虑有障碍的影响。一旦行或列中出现了障碍格子,后面的格子都不可达。
- 在更新到达(i,j)格子时,要注意查看(i,j-1)和(i-1,j)是否是障碍格子,并分别处理。
代码:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) { //c++ int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); int array[m][n]; //init bool haveObs = false; for(int i = 0; i < n; i++){ if(obstacleGrid[0][i] == 0 && !haveObs){ array[0][i] = 1; continue; } else if(obstacleGrid[0][i] == 1){ haveObs = true; } array[0][i] = 0; } haveObs = false; for(int i = 0; i < m; i++) { if(obstacleGrid[i][0] == 0 && !haveObs){ array[i][0] = 1; continue; } else if(obstacleGrid[i][0 ==1]){ haveObs = true; } array[i][0] = 0; } for(int i = 1; i < m; i++) for(int j = 1; j < n; j++){ array[i][j] = 0; if(obstacleGrid[i][j] == 1) continue; if(obstacleGrid[i-1][j] == 0) array[i][j] += array[i-1][j]; if(obstacleGrid[i][j-1] == 0) array[i][j] +=array[i][j-1]; } return array[m-1][n-1]; }
[leetcode]Unique Paths II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。