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

Categories:

题目描述
思路分析
1. 解法一：记忆化 DFS（推荐）
相似题目

题目描述

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

思路分析

解法一：记忆化 DFS（推荐）

核心思路：

从终点递归回溯到起点，只能向上或向左移动。

用 failed 标记无法到达起点的格子，避免重复搜索。

回溯成功时将路径加入结果。

复杂度分析：

时间复杂度：O(mn)，其中 m、n 表示网格行列数。

空间复杂度：O(mn)，递归栈与失败标记。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        List<List<Integer>> path = new ArrayList<>();
        if (obstacleGrid == null || obstacleGrid.length == 0) {
            return path;
        }

        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        boolean[][] failed = new boolean[m][n];

        if (dfs(obstacleGrid, m - 1, n - 1, path, failed)) {
            return path;
        }
        return new ArrayList<>();
    }

    private boolean dfs(int[][] grid, int x, int y, List<List<Integer>> path, boolean[][] failed) {
        if (x < 0 || y < 0 || grid[x][y] == 1 || failed[x][y]) {
            return false;
        }

        if (x == 0 && y == 0) {
            path.add(List.of(0, 0));
            return true;
        }

        if (dfs(grid, x - 1, y, path, failed) || dfs(grid, x, y - 1, path, failed)) {
            path.add(List.of(x, y));
            return true;
        }

        failed[x][y] = true;
        return false;
    }
}

func pathWithObstacles(obstacleGrid [][]int) [][]int {
	path := make([][]int, 0)
	if len(obstacleGrid) == 0 || len(obstacleGrid[0]) == 0 {
		return path
	}

	m, n := len(obstacleGrid), len(obstacleGrid[0])
	failed := make([][]bool, m)
	for i := range failed {
		failed[i] = make([]bool, n)
	}

	var dfs func(x, y int) bool
	dfs = func(x, y int) bool {
		if x < 0 || y < 0 || obstacleGrid[x][y] == 1 || failed[x][y] {
			return false
		}
		if x == 0 && y == 0 {
			path = append(path, []int{0, 0})
			return true
		}
		if dfs(x-1, y) || dfs(x, y-1) {
			path = append(path, []int{x, y})
			return true
		}
		failed[x][y] = true
		return false
	}

	if dfs(m-1, n-1) {
		return path
	}
	return [][]int{}
}

相似题目

题目	难度	考察点
面试题 08.02. 迷路的机器人	中等	DFS
62. 不同路径	中等	DP
63. 不同路径 II	中等	DP
64. 最小路径和	中等	DP
200. 岛屿数量	中等	DFS
1091. 二进制矩阵中的最短路径	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/54445111