Description
Submission
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if(obstacleGrid[0][0] == 1) return 0;
int nRow = obstacleGrid.size();
int nCol = obstacleGrid[0].size();
vector<vector<int>> dp(nRow, vector<int>(nCol, 0));
bool isBlocked = false;
for(int i = 0; i < nRow; ++i) {
if(obstacleGrid[i][0] == 1) isBlocked = true;
if(!isBlocked) dp[i][0] = 1;
else dp[i][0] = 0;
}
isBlocked = false;
for(int j = 1; j < nCol; ++j) {
if(obstacleGrid[0][j] == 1) isBlocked = true;
if(!isBlocked) dp[0][j] = 1;
else dp[0][j] = 0;
}
for(int i = 1; i < nRow; ++i) {
for(int j = 1; j < nCol; ++j) {
if(obstacleGrid[i][j] == 1) continue;
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[nRow-1][nCol-1];
}
};
Submission 210625
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
dp[0][0] = 1;
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(obstacleGrid[i][j]) {
dp[i][j] = 0;
continue;
}
if(i != 0) dp[i][j] += dp[i-1][j];
if(j != 0) dp[i][j] += dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};