🤖 迷路的机器人
设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。设计一种算法，寻找机器人从左上角移动到右下角的路径。
网格中的障碍物和空位置分别用 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
36
37
38
39
40
41
42
43
44
45
46
| class Solution {
//使用回溯来做，每次到达当前位置，有两个位置可以走，一旦走到了最后的位置，就可以返回结果
//还是一旦有一个结果就直接返回
List<List<Integer>> path=new ArrayList<>();
List<List<Integer>> res=new ArrayList<>();
public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
//起点有障碍物直接返回空数组
if(obstacleGrid[0][0]==1)
return res;
List<Integer> temp=new ArrayList<>();
temp.add(0);
temp.add(0);
path.add(temp);
backtrack(obstacleGrid,0,0);
//如果没有到达终点，res不会赋值，就是空数组
return res;
}
//回溯法统计所有的结果
private boolean backtrack(int[][] obstacleGrid,int row,int column){
//到达终点
if(row==obstacleGrid.length-1&&column==obstacleGrid[0].length-1){
res=new ArrayList(path);
return true;
}
int[][] index=new int[][]{{0,1},{1,0}};
//选择一个方向，向右或者向下，默认先选向右
for(int i=0;i<2;++i){
int newRow=row+index[i][0];
int newColumn=column+index[i][1];
//当前位置没超过范围并且没有障碍物才尝试回溯
if(newRow<obstacleGrid.length&&newColumn<obstacleGrid[0].length
&&obstacleGrid[newRow][newColumn]!=1){
List<Integer> temp=new ArrayList<>();
temp.add(newRow);
temp.add(newColumn);
path.add(temp);
if(backtrack(obstacleGrid,newRow,newColumn)){
return true;
}
//开始回溯
path.remove(path.size()-1);
}
}
return false;
}
}
|
按照上面的代码执行之后会超时，下面考虑剪枝的问题
上面的代码超时主要是因为走了很多重复的路径，如果从一个点[x,y]出发走不到终点，需要慢慢回溯，如果回溯到一个点，然后向下时继续走到了[x,y]，由于没有增加判断机制，所以又会重新从[x,y]继续向下走，造成了重复的遍历，如果增加一个成功数组，如果从[x,y]出发没有到达终点，那么这一路的成功数组都为true，这样回溯之后走到这一条路就不会再走了
换一种说法就是回溯之后遇到了之前遍历过的节点，说明这一条路走过了，并且没有到达终点，如果这条路向下到达终点就不会回溯，所以这条路不能走了
一旦在回溯的过程中遇到了访问过的节点说明当前节点向下不能到达终点，否则早返回了
新的代码为：
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
//使用回溯来做，每次到达当前位置，有两个位置可以走，一旦走到了最后的位置，就可以返回结果
//还是一旦有一个结果就直接返回
List<List<Integer>> path=new ArrayList<>();
List<List<Integer>> res=new ArrayList<>();
public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
//起点有障碍物直接返回空数组
if(obstacleGrid[0][0]==1)
return res;
List<Integer> temp=new ArrayList<>();
temp.add(0);
temp.add(0);
path.add(temp);
//这个访问数组是为了剪枝
boolean[][] used=new boolean[obstacleGrid.length][obstacleGrid[0].length];
backtrack(obstacleGrid,0,0,used);
//如果没有到达终点，res不会赋值，就是空数组
return res;
}
//回溯法统计所有的结果
private boolean backtrack(int[][] obstacleGrid,int row,int column,boolean[][] used){
//到达终点
if(row==obstacleGrid.length-1&&column==obstacleGrid[0].length-1){
res=new ArrayList(path);
return true;
}
int[][] index=new int[][]{{0,1},{1,0}};
//选择一个方向，向右或者向下，默认先选向右
for(int i=0;i<2;++i){
int newRow=row+index[i][0];
int newColumn=column+index[i][1];
//当前位置没超过范围并且没有障碍物才尝试回溯
if(newRow<obstacleGrid.length&&newColumn<obstacleGrid[0].length
&&obstacleGrid[newRow][newColumn]!=1&&!used[newRow][newColumn]){
List<Integer> temp=new ArrayList<>();
temp.add(newRow);
temp.add(newColumn);
path.add(temp);
used[newRow][newColumn]=true;
if(backtrack(obstacleGrid,newRow,newColumn,used)){
return true;
}
//开始回溯,只删除路径，不回复used，这样告知后面的节点，这条路行不通
path.remove(path.size()-1);
}
}
return false;
}
}
|
执行流程
主要是回溯法的执行流程：
- 要从
[0,0]点开始出发，首先先将这个点加入路径中 - 对于当前节点来说，只能向下或者向右，如果向下可以并且不是障碍，没访问过，那么就可以访问
- 向右同理
- 只要找到一条合法的路径，就直接向上一路返回，最终返回得到的结果
- 如果最终都没有找到合法的路径，那么res压根不会保存任何一条路径
- 最终直接返回res即可
总结
主要是当前问题不是求有多少条路径数或者最短的路径数是什么，所以不能使用动态规划，考虑递归并编写代码之后，出现了超时的问题，考虑到当前没有剪枝，于是提出了这种记录当前节点是否能够到达终点的数组，一旦在回溯的过程中遇到了访问过的节点说明当前节点向下不能到达终点，否则早返回了