首页 > 代码库 > 63. Unique Paths II
63. 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.
1 class Solution { 2 public: 3 int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { 4 if(obstacleGrid.empty() || obstacleGrid[0].empty()){ 5 return 0; 6 } 7 int row = obstacleGrid.size(); 8 int col = obstacleGrid[0].size(); 9 10 int dp[row][col];11 12 dp[0][0] = (obstacleGrid[0][0] == 0 ? 1 : 0);13 14 for(int i = 1; i < row; i++){15 dp[i][0] = ((dp[i-1][0] == 1 && obstacleGrid[i][0] == 0)? 1 : 0);16 }17 18 for(int j = 1; j < col; j++){19 dp[0][j] = ((dp[0][j-1] == 1 && obstacleGrid[0][j] == 0)? 1: 0);20 }21 22 for(int i = 1 ; i < row; i++){23 for(int j = 1 ; j < col;j++){24 if(obstacleGrid[i][j] == 1){25 dp[i][j] = 0;26 }else{27 dp[i][j] = dp[i-1][j]+dp[i][j-1];28 }29 }30 }31 32 return dp[row-1][col-1];33 }34 };
63. Unique Paths II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。