# C++ simple dp solution. NO extra vector. With comments

• The idea is simple. You have to transform original grid to a dp grid.
If a cell is blocked, you have to say that there's no way to get into that cell and block the following cells depending on that cell.

``````int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
bool Xhas1 = false, Yhas1 = false;
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
// If first cell is blocked or vector empty, there are no paths
if(!m || obstacleGrid[0][0] == 1) {
return 0;
}
else { // There is 1 path to get to the first cell
obstacleGrid[0][0] = 1;
}
// For each row
for(int i = 1; i < m; i++){
// If there is a blocking road before, there's no way to get to rows below
if(Yhas1) obstacleGrid[i][0] = 0;
// If this is blocked, you have to block the following cells and indicate there's no path here
else if(obstacleGrid[i][0] == 1) {
obstacleGrid[i][0] = 0;
Yhas1 = true;
}
// There's one path to get to this cell
else obstacleGrid[i][0] = 1;
}

// Same idea as row, but for columns
for(int i = 1; i < n; i++){
if(Xhas1) obstacleGrid[0][i] = 0;
else if(obstacleGrid[0][i] == 1) {
obstacleGrid[0][i] = 0;
Xhas1 = true;
}
else obstacleGrid[0][i] = 1;
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++) {
// If the cell is blocked, there's no way to get to the cell
if(obstacleGrid[i][j] == 1) obstacleGrid[i][j] = 0;
else {
// Just normal dp
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
}
}
}
return obstacleGrid[m - 1][n - 1];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.