😄63.不同路径II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的**障碍物（1）和空位置（0）**分别用 1 和 0 来表示。
相比于62题，只是多了一个障碍物，相当于有的网格去不了
思路
基本思想
相比于
62题
，只是多了一个障碍物，所以在统计时需要注意，有两种情况需要单独处理：
- 如果当前网格有障碍物，那么就不用统计
- 如果当前网格的左边或者上边有障碍物，那么只需要统计没有障碍物的一方
其余的思路和62题一样，确定递归方程和初始化第一行和第一列，第一行和第一列有可能也有障碍
题中给定了一个二维容器vector，当容器中的元素为0代表没有障碍，容器中的元素为1代表有障碍
统计时遇到障碍，到达当前网格的路径数就是0，
执行流程
由于题中给出一个二维容器，所以不需要再初始化一个二维vector，只需要将给定容器的第一行和第一列初始化即可，之后利用递推方程f(m,n)=f(m-1,n)+f(m,n-1)将每个网格的路径数进行统计即可
统计时需要判断当前网格是否有障碍
初始化第一行第一列时，由于有障碍，一旦出现障碍，后面的网格都无法到达，也就是路径数为0
左上角网格不可以初始化两次，需要单独判断
从第二行第二列开始统计，当前网格出现障碍，到达他的路径数就为0
当前网格没有障碍时，上方和左方不管有没有障碍直接统计，有障碍路径数为0也没有影响
代码
根据以上分析，得出以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
obstacleGrid[0][0]=obstacleGrid[0][0]==1?0:1;
int row=obstacleGrid.size();
int column=obstacleGrid[0].size();
for(int i=1;i<column;++i){//第一行
if(obstacleGrid[0][i]!=1){//没障碍
obstacleGrid[0][i]=obstacleGrid[0][i-1];//于左边的网格有关
}else{//有障碍
obstacleGrid[0][i]=0;
}
}
for(int i=1;i<row;++i){//第一列
if(obstacleGrid[i][0]!=1){//没障碍
obstacleGrid[i][0]=obstacleGrid[i-1][0];//与上面的网格有关
}else{//有障碍
obstacleGrid[i][0]=0;//到达当前网格的路径数为0
}
}
//从第二行第二列开始统计
for(int i=1;i<row;++i){//行
for(int j=1;j<column;++j){//列
if(obstacleGrid[i][j]==1){//当前网格有障碍
obstacleGrid[i][j]=0;//到达当前网格的路径数为0
}else{//没有障碍
int upper=obstacleGrid[i-1][j];
int left=obstacleGrid[i][j-1];
obstacleGrid[i][j]=upper+left;
}
}
}
return obstacleGrid[row-1][column-1];
}
};
|
总结
编写代码时需要注意以下几点：
- 左上角网格不能初始化两次，需要单独处理
- 初始化第一行和第一列时，一旦出现障碍物，后面的网格都不可达，不可达的路径数为0
- 统计时如果当前网格出现障碍，那么当前网格的路径数为0，统计时上方和左方不管是否有障碍都可以直接应用递推公式，因为有障碍代表路径数为0，没有任何影响