这是之前一个算法的升级版本。
之前题目:一个机器人在 m × n 的网格中的左上角(在下面示意图中标记 'Start' 的位置)。
在同一时间点中,机器人只能向下或者向右走。机器人的目标是右下角(用 'Finish' 标记的位置)
问:有多少种不同的路线?
本题题目:现在如果我们给栅格中加入了障碍,那会有多少种不同的路径呢?
在栅格中障碍标记为 1,空格标记为 0。
例如,
下面是在 3 × 3 的栅格正中央有一个障碍的情况:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
不同的路径数是 2。
注意: m 和 n 都 <= 100.
思路:
这题和上一题不同在于有了障碍,所以关键在于对障碍的分析:
① 遇到障碍把障碍的值设为 0 代表无法到达这一点
② 初始化第一行第一列的时候若遇到障碍,把障碍后面的数也都置为 0(因为后面永远无法到达)
代码:
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;
else if(j == 0)
obstacleGrid[i][j] = obstacleGrid[i - 1][j] * 1;
else
//当前位置 = 左边 + 上面
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
}
}
return obstacleGrid[rows - 1][cols - 1];
}
复杂度:空间复杂度O(n),时间复杂度O(raw*cols)
网友评论