let uniquePathsWithObstacles = function(obstacleGrid) {
if (!obstacleGrid || !obstacleGrid.length) return 0;
function markNextRowsAsZero(col) {
for (let i = col; i < maxCol; i++) {
obstacleGrid[0][i] = 0;
}
}
function markNextColumnsAsZero(row) {
for (let i = row; i < maxRow; i++) {
obstacleGrid[i][0] = 0;
}
}
let maxRow = obstacleGrid.length,
maxCol = obstacleGrid[0].length,
OBSTACLE = 1, VISITED = -1;
// first block is obstacle return 0;
if (obstacleGrid[0][0] === OBSTACLE) {
return 0;
}
// mark all first rows as either 1 or zero
for (let col = 0; col < maxCol;col++) {
if (obstacleGrid[0][col] === OBSTACLE) {
markNextRowsAsZero(col);
break;
}
else {
obstacleGrid[0][col] = 1;
}
}
// mark all first columns as either 1 or zero
for (let row = 1; row < maxRow;row++) {
if (obstacleGrid[row][0] === OBSTACLE) {
markNextColumnsAsZero(row);
break;
}
else {
obstacleGrid[row][0] = 1;
}
}
for (let row = 1; row < maxRow;row++) {
for (let col = 1; col < maxCol;col++) {
if (obstacleGrid[row][col] === OBSTACLE) {
obstacleGrid[row][col] = 0;
}
else {
obstacleGrid[row][col] =
obstacleGrid[row - 1][col] +
obstacleGrid[row][col - 1];
}
}
}
return obstacleGrid[maxRow - 1][maxCol - 1];
};
Categories