T63. Unique Paths II【Medium】
題目
在上一題的基礎上：
現(xiàn)在如果我們給柵格中加入了障礙茬贵，那會有多少種不同的路徑呢槐沼？
在柵格中障礙標記為 1阶冈，空格標記為 0。
例如葫慎，
下面是在 3 × 3 的柵格正中央有一個障礙的情況：
[
[0,0,0],
[0,1,0],
[0,0,0]
]
不同的路徑數(shù)是 2衔彻。
注意： m 和 n 都 <= 100.
思路
這題和上一題差不多，變得在于有了障礙偷办，所以關鍵在于對障礙的分析：
① 遇到障礙把障礙的值設為 0 代表無法到達這一點
② 初始化第一行第一列的時候若遇到障礙艰额，把障礙后面的數(shù)也都置為 0（因為后面永遠無法到達）
代碼
代碼取自 Top Solution，稍作注釋
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//若傳入值為空椒涯，則返回0
if(obstacleGrid.length == 0) return 0;
//得到行列的長度
int rows = obstacleGrid.length;
int cols = obstacleGrid[0].length;
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
//若為1則設為 0
if(obstacleGrid[i][j] == 1)
obstacleGrid[i][j] = 0;
//把第一個點設為1
else if(i == 0 && j == 0)
obstacleGrid[i][j] = 1;
//第一行第一列中若有存在障礙柄沮，則它后面的都為0（不可達到）
else if(i == 0)
obstacleGrid[i][j] = obstacleGrid[i][j - 1] * 1;// For row 0, if there are no paths to left cell, then its 0,else 1
else if(j == 0)
obstacleGrid[i][j] = obstacleGrid[i - 1][j] * 1;// For col 0, if there are no paths to upper cell, then its 0,else 1
else
//當前位置 = 左邊 + 上面
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
}
}
return obstacleGrid[rows - 1][cols - 1];
}
