LeetCode 面试题 08.02. 迷路的机器人

约 6 分钟
文章信息 9 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 程序员面试金典（第 6 版） 字节 快手 旷视
标签
数组 动态规划 矩阵 回溯

题目描述

✅ 面试题 08.02. 迷路的机器人

image-20260929000723631

题意分析

网格中 0 表示可走、1 表示障碍。机器人从左上角出发，只能向下或向右移动，返回一条按经过顺序记录坐标的完整路径，包含起点和右下角终点；若无法到达，返回空列表。

解法：回溯加失败位置剪枝

核心思路

[!blue]

令 dfs(row, col) 表示尝试从当前格继续走到终点。进入一个合法格子后，把坐标加入 path，此时 path 恰好记录从起点走到当前格的路线。接着先向下、再向右搜索：任一方向成功，就保留路径并向上返回成功；两个方向都失败，才移除当前坐标，恢复进入本层前的路径。

同一个格子可能由上方和左方的不同路线到达，但它后面能否到达终点，只取决于这个格子以及右下方的障碍，与此前怎么走来无关。因此一个格子确认走不通之后，其他路线再到这里也不必重复搜索，可以保留访问标记剪枝。

代码在进入格子时就将 visited 置为 true，而不是等失败后才标记，这仍然正确。每次移动都会让 row + col 增大，所以不可能回到当前递归路径上的祖先。以后再次遇到已访问格子时，它只能来自一个已经结束的旧分支；若那个分支成功，成功结果早已沿调用链返回，整个搜索也会停止。因此搜索仍在继续就说明旧分支已经失败，可以直接剪掉。

path 与 visited 的用途不同：前者只保留当前这条候选路线，失败时必须回退；后者用于避免重复展开已经搜索过的位置，不能随路径一起撤销。这样每个可走格子最多展开一次。

越界、障碍、已访问位置直接返回失败，且不加入路径。终点则在入路径后立即返回成功，保证结果包含终点。若起点或终点是障碍，就找不到路径；网格只有一个格子且它可走时，加入起点后也就已经到达终点。

解题步骤

  1. 空网格直接返回空列表，否则建立与网格同尺寸的 visited，从 (0, 0) 开始搜索。
  2. 进入递归先检查当前位置；只要越界、遇到障碍或已经访问，就返回 false。
  3. 将当前位置加入 path 并标记访问；若已经到达右下角，返回 true。
  4. 依次搜索下方与右方，任一成功就立即返回 true，不撤销已找到的路径。
  5. 两个方向都失败，移除本层加入的坐标并返回 false。起点搜索成功时返回保留的路径，否则返回空列表。

代码实现

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)$，其中 m、n 是网格的行数与列数。每个可走格子最多展开一次，每次只尝试两个方向；重复访问或无效位置会立即返回。
  • 空间复杂度：$O(mn)$。访问表占 $O(mn)$，当前路径和递归栈最长为 $O(m+n)$，因为只能向右或向下。

关键点总结

[!green]

  • 路径入栈与失败回退成对出现，成功时沿调用链保留完整结果。
  • 无环的移动规则与成功后的立即返回，保证后续重遇已访问位置时可以按失败处理。
  • 每个位置后面的可达性与来路无关，保留访问标记才能消除重复搜索。

易错点总结

[!yellow]

  • 无论成功失败都弹出坐标，会把已经找到的答案清空；失败时不弹出，又会把死路混进结果。
  • 把 visited 当作当前路径标记并在回溯时清除，会反复搜索同一个失败位置。
  • 必须先排除障碍，再判断终点，不能把有障碍的右下角当成合法终点。
  • 下方成功后要立即停止；继续探索并修改同一个 path 会破坏已经得到的结果。

相似题目

题目 难度 关联与区别
63. 不同路径 II 中等 移动和障碍规则相近，原题统计路径条数，本题只需返回一条可行路径。
64. 最小路径和 中等 原题还最小化路径代价，本题没有权值优化，只要记录一条可达前驱链。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/54445111
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！