Leetcode 63. Unique Paths II
文章作者：Tyan
博客：noahsnail.com | **** | 简书
1. Description
2. Solution
- Version 1
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> path(m, vector<int>(n));
path[0][0] = 1;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(obstacleGrid[i][j]) {
path[i][j] = 0;
continue;
}
if(i > 0 && j > 0) {
path[i][j] = path[i - 1][j] + path[i][j - 1];
}
else if(i < 1 && j > 0) {
path[i][j] = path[i][j - 1];
}
else if(i > 0 && j < 1) {
path[i][j] = path[i - 1][j];
}
}
}
return path[m - 1][n - 1];
}
};
- Version 2
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
if(!obstacleGrid[0][0]) {
obstacleGrid[0][0] = 1;
}
else {
obstacleGrid[0][0] = 0;
}
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(i == 0 && j == 0) {
continue;
}
if(obstacleGrid[i][j]) {
obstacleGrid[i][j] = 0;
continue;
}
if(i > 0 && j > 0) {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
}
else if(i < 1 && j > 0) {
obstacleGrid[i][j] = obstacleGrid[i][j - 1];
}
else if(i > 0 && j < 1) {
obstacleGrid[i][j] = obstacleGrid[i - 1][j];
}
}
}
return obstacleGrid[m - 1][n - 1];
}
};