T63. Unique Paths II【Medium】
题目
在上一题的基础上：
现在如果我们给栅格中加入了障碍，那会有多少种不同的路径呢？
在栅格中障碍标记为 1，空格标记为 0。
例如，
下面是在 3 × 3 的栅格正中央有一个障碍的情况：
[
[0,0,0],
[0,1,0],
[0,0,0]
]
不同的路径数是 2。
注意： m 和 n 都 <= 100.
思路
这题和上一题差不多，变得在于有了障碍，所以关键在于对障碍的分析：
① 遇到障碍把障碍的值设为 0 代表无法到达这一点
② 初始化第一行第一列的时候若遇到障碍，把障碍后面的数也都置为 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];
}
