LeetCode 面试题 08.02. 迷路的机器人
目录
题目描述
题意分析
给定一个
m × n的网格，0表示可以通过、1表示障碍。机器人从左上角(0, 0)出发，每一步只能向右或向下，要求返回一条到达右下角(m - 1, n - 1)的路径，路径以坐标列表的形式给出，起点和终点都要包含在内；若不存在这样的路径，返回空列表。注意这题要的是任意一条可行路径，不是最短路径、不是路径数量、也不是所有路径。只要找到一条就可以立刻收工，这决定了整个算法可以「一旦成功就短路返回」。
「只能向右或向下」这个限制信息量极大：行号与列号都只增不减，机器人永远不可能回到走过的格子，也不可能绕圈。换句话说，格子之间的可达关系构成一张有向无环图，这直接排除了成环的顾虑，也让状态标记不必在回退时清除。
更进一步的推论是无后效性：一个格子能不能走到终点，只取决于它自己和它右下方的格局，与「机器人是怎么走到这个格子的」毫无关系。因此某个格子一旦被判定为「走不通」，这个结论就永久成立，任何路径再次经过它都不必重新验证。这是把指数级搜索压成线性的关键。
数据规模上，网格边长在百的量级，路径条数最多可达组合数 $C_{m+n}^{n}$ 那么多，逐条枚举必然超时；但格子总数只有
m × n，围绕格子而不是围绕路径来做文章才有出路。边界：起点或终点本身是障碍时无解，返回空列表；网格为空或首行为空时同样返回空列表。
解法：回溯加失败位置剪枝
核心思路
最直接的想法是枚举所有由「右」「下」组成的走法，每条走完再看是不是合法。路径总数是组合数级别的，
m = n = 20时就已经上亿，完全不可行。瓶颈在于同一个格子会被无数条不同的前缀路径重复展开，而每次展开得到的结论完全相同。上面已经论证过：由于只能右下移动，「从某格出发能否到终点」与前缀无关。既然结论可复用，那就把它记下来。
于是引入
visited数组，但它的语义不是通常意义上的「这个格子来过」，而是——visited[r][c] == true表示已经以该格为起点搜索过，并且确认它走不到终点。之所以能这样解释，是因为一旦某次搜索成功，函数会一路return true直接返回到最外层，绝不会再有第二次查询发生；只有失败的格子才会被后续分支撞见。有了这个标记，每个格子至多被真正展开一次，总工作量降到 $O(mn)$。路径的维护采用「进入时压入、失败时弹出、成功时保留」的回溯模式，不变量是：
path在任意时刻都恰好保存着从起点走到当前格子的一条合法路径（全是0格，且每步都是向右或向下）。进入一个格子先把它压进path，如果它就是终点，那么此刻path正好是一条完整答案，直接返回true并且不再弹出任何元素；如果两个方向都失败，说明这一格无法通向终点，就把它弹出、打上失败标记，恢复到进入前的状态。搜索方向固定为「先下后右」，这只影响最终返回的是哪一条路径，不影响是否有解——题目接受任意一条，所以两种顺序都对。
顺便说一句，这题也能用「从右下往左上推」的动态规划求出每格是否可达，再顺着可达标记回溯出路径；但本解法的写法更短，且
visited剪枝已经让复杂度与动态规划持平。
解题步骤
- 处理空输入：网格为
null、行数为0或列数为0时直接返回空列表，避免后续取grid[0].length时越界。- 准备路径列表与失败标记数组：
path收集答案坐标，visited与网格同形，初值全false。- 从起点发起搜索：调用
dfs(grid, 0, 0, visited, path)，成功返回path，失败返回一个新的空列表。起点是障碍的情况不需要特判，会被dfs内部的障碍判断吃掉。- 四个失败条件合并成一行：
row >= 行数、col >= 列数、grid[row][col] == 1、visited[row][col]，任一成立就返回false。因为行列只增不减，不可能出现负下标，所以不必判断row < 0；但越界判断必须排在读取grid[row][col]之前，否则会数组越界。- 压入当前格并打标记：
path.add(...)与visited[row][col] = true。这里先打标记不会误伤自己，因为向右向下永远不会绕回当前格。- 命中终点立即返回
true：此时path的最后一个元素正是终点，整条路径已经完整，必须在这里返回，否则会继续往界外试探并最终把终点弹出去。- 依次尝试向下、向右：
dfs(row + 1, col) || dfs(row, col + 1)，短路求值保证一旦向下成功就不再尝试向右。任一成功就return true把成功信号一路传上去，path原样保留。- 两个方向都失败则弹出当前格：
path.remove(path.size() - 1)恢复现场，返回false。此时visited标记保留不清除——这正是剪枝生效的地方，也是本题与普通网格回溯（如单词搜索）最大的写法差异。以下面这个
3 × 3网格走一遍，其中(1, 1)与(2, 0)是障碍。
[[0, 0, 0], [0, 1, 0], [1, 0, 0]]进入
(0, 0)：合法，压入，path = [[0,0]]，不是终点，先向下。
进入(1, 0)：合法，压入，path = [[0,0], [1,0]]，不是终点，先向下。
进入(2, 0)：grid[2][0] == 1是障碍，返回false。
回到(1, 0)尝试向右，进入(1, 1)：也是障碍，返回false。
(1, 0)两个方向皆败，弹出它，path回到[[0,0]]，并保留visited[1][0] = true——从此这个格子被永久判死。
回到(0, 0)尝试向右，进入(0, 1)：合法，压入，path = [[0,0], [0,1]]，先向下进入(1, 1)，障碍，失败；转向右。
进入(0, 2)：合法，压入，path = [[0,0], [0,1], [0,2]]，先向下。
进入(1, 2)：合法，压入，path = [[0,0], [0,1], [0,2], [1,2]]，不是终点，先向下。
进入(2, 2)：合法，压入，path = [[0,0], [0,1], [0,2], [1,2], [2,2]]，命中终点，返回true。
true一路短路上传，沿途不再执行任何弹出操作，最外层直接把path返回，答案就是[[0,0], [0,1], [0,2], [1,2], [2,2]]。再看一个无解的例子
[[0, 0, 0], [0, 0, 1], [0, 1, 0]]：终点(2, 2)被(1, 2)和(2, 1)两个障碍彻底封死。搜索会依次把(2, 0)、(1, 1)、(1, 0)、(0, 2)、(0, 1)、(0, 0)判死并逐个弹出，其中(0, 1)向下走到(1, 1)时直接命中visited剪枝、一次都没有重新展开。最终dfs返回false，path也已被弹空，函数返回空列表。
代码实现
class Solution {
public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
List<List<Integer>> path = new ArrayList<>();
if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
return path;
}
boolean[][] visited = new boolean[obstacleGrid.length][obstacleGrid[0].length];
if (dfs(obstacleGrid, 0, 0, visited, path)) {
return path;
}
return new ArrayList<>();
}
private boolean dfs(int[][] grid, int row, int col, boolean[][] visited, List<List<Integer>> path) {
if (row >= grid.length || col >= grid[0].length || grid[row][col] == 1 || visited[row][col]) {
return false;
}
path.add(Arrays.asList(row, col));
visited[row][col] = true;
if (row == grid.length - 1 && col == grid[0].length - 1) {
return true;
}
if (dfs(grid, row + 1, col, visited, path) || dfs(grid, row, col + 1, visited, path)) {
return true;
}
path.remove(path.size() - 1);
return false;
}
}
func pathWithObstacles(obstacleGrid [][]int) [][]int {
path := [][]int{}
if len(obstacleGrid) == 0 || len(obstacleGrid[0]) == 0 {
return path
}
rows, cols := len(obstacleGrid), len(obstacleGrid[0])
visited := make([][]bool, rows)
for i := 0; i < rows; i++ {
visited[i] = make([]bool, cols)
}
var dfs func(int, int) bool
dfs = func(row int, col int) bool {
if row >= rows || col >= cols || obstacleGrid[row][col] == 1 || visited[row][col] {
return false
}
path = append(path, []int{row, col})
visited[row][col] = true
if row == rows-1 && col == cols-1 {
return true
}
if dfs(row+1, col) || dfs(row, col+1) {
return true
}
path = path[:len(path)-1]
return false
}
if dfs(0, 0) {
return path
}
return [][]int{}
}
复杂度分析
- 时间复杂度：$O(mn)$。每个格子至多被真正展开一次——成功的格子会让搜索立刻结束，失败的格子被
visited永久标记后再也不会重新展开；每次展开只做常数次判断和两次子调用，所以总量与格子数同阶。若去掉visited，复杂度会退化到路径条数级别的 $O(C_{m+n}^{n})$。- 空间复杂度：$O(mn)$，
visited数组占 $O(mn)$；递归栈深度最多是一条路径的长度 $O(m + n)$；path最长也是 $O(m + n)$。三者之和由visited主导。
关键点总结
- 先判断有没有后效性：只能右下移动 ⇒ 「能否到终点」与来路无关 ⇒ 结论可缓存。这个推理链是把回溯从指数级压到线性级的通用路径，遇到网格搜索题应当第一时间检查。
- 想清楚标记数组的语义：这里的
visited是「已确认走不通」，不是「来过」，所以回退时不清除。与之相对，单词搜索那类允许四方向的题必须在回退时清除标记，否则会漏解。语义决定写法，背模板最容易在这里翻车。- 成功与失败的收尾方式不同：失败弹出、成功保留，靠
return true一路短路来实现「不再弹出」。凡是「找到一个解就收工」的搜索，都可以用布尔返回值 + 短路的写法，比抛异常或设全局标志位干净。- 合并边界判断的顺序不能乱：越界检查必须写在访问
grid[row][col]之前，短路求值才是安全的。- 面试视角：这题的区分度不在能不能写出 DFS，而在能否主动说明「为什么
visited不用回退清除」以及「不加visited会退化成什么复杂度」。如果面试官追问其他解法，可以答：由于只能右下走，从右下角往左上角递推每个格子是否可达是等价的动态规划，再顺着可达标记走一遍即可还原路径，复杂度同为 $O(mn)$。
易错点总结
- 成功时也弹出路径：把
path.remove(...)写在函数出口统一执行，返回true之后路径又被逐层弹空，[[0]]这种一格网格会返回空列表而不是[[0,0]]。- 失败时忘记弹出路径：走不通的格子留在了
path里，[[0,0,0],[0,1,0],[1,0,0]]会把死胡同(1, 0)混进答案，输出一条根本走不通的路径。- 回退时把
visited清掉：剪枝彻底失效，退化成枚举所有右下走法，100 × 100的全0网格直接超时。这正是从单词搜索那类题里照搬模板最容易犯的错。- 到达终点后不立即返回
true：继续向下、向右试探，两个方向都越界返回false，于是终点被当作失败格弹出，[[0]]会返回空列表。- 越界判断与取值判断顺序写反：把
visited[row][col]或grid[row][col] == 1放在row >= 行数之前，走到边界外时直接数组越界异常。- 先压入路径再判断障碍：起点是障碍时
[[1,0],[0,0]]会返回[[0,0]]这样一条含障碍的非法路径，正确答案是空列表。- 多写了向上、向左两个方向：题目只允许右和下，四方向搜索出来的路径可能先向右再向上，
[[0,0,0],[0,1,0],[1,0,0]]上会输出不满足题意的路径，并且无后效性不再成立、visited剪枝也随之失效。- 误把题目当成求路径数量：写成
unique-paths那样的递推返回计数，题目要的是具体坐标序列，答非所问。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 63. 不同路径 II | 中等 | 同样是带障碍的右下移动，但求方案数量，用递推而不必还原路径 |
| 62. 不同路径 | 中等 | 无障碍版本，可直接用组合数公式，是本题的最简形态 |
| 64. 最小路径和 | 中等 | 移动方向相同，但目标从可行性变成权值最优，需比较两条来路 |
| 980. 不同路径 III | 困难 | 四方向且必须走遍所有空格，visited 必须在回退时清除 |
| 79. 单词搜索 | 中等 | 四方向搜索的典型代表，对照理解「标记何时该清除」 |
| 剑指 Offer 13. 机器人的运动范围 | 中等 | 障碍换成数位和阈值，求可达格子总数而非某一条路径 |
| 1926. 迷宫中离入口最近的出口 | 中等 | 四方向且要求最短，必须换成广度优先搜索 |
| 200. 岛屿数量 | 中等 | 同为网格深搜，目标是统计连通块，标记一律不回退 |