首页 > 代码库 > Unique Paths II <leetcode>
Unique Paths II <leetcode>
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.
算法：一开始理解错了，以为到一个点可以从上下左右，写了一个非常复杂的代码，后来自己感觉不对，上网上一查才发现，原来还是到一个点只能从上或左，那这道题就非常简单了，思路和第一个版本是一样的，只是增加了障碍物，所以计算的时候，考虑一下障碍物就行了，代码如下（动态规划）：
1 class Solution { 2 public: 3 int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) { 4 vector<vector<int>> f(obstacleGrid.size(),vector<int>(obstacleGrid[0].size())); 5 f[0][0]=obstacleGrid[0][0]==0?1:0; 6 for(int i=1;i<f.size();i++) 7 { 8 f[i][0]=obstacleGrid[i][0]==0?f[i-1][0]:0; 9 }10 for(int i=1;i<obstacleGrid[0].size();i++)11 {12 f[0][i]=obstacleGrid[0][i]==0?f[0][i-1]:0;13 }14 15 for(int i=1;i<obstacleGrid.size();i++)16 {17 for(int j=1;j<obstacleGrid[0].size();j++)18 {19 f[i][j]=obstacleGrid[i][j]==0?(f[i-1][j]+f[i][j-1]):0;20 }21 }22 return f[f.size()-1][f[0].size()-1];23 }24 };
Unique Paths II <leetcode>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。