LeetCode 题解工作台
逃离大迷宫
在一个 10 6 x 10 6 的网格中，每个网格上方格的坐标为 (x, y) 。 现在从源方格 source = [s x , s y ] 开始出发，意图赶往目标方格 target = [t x , t y ] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [x i…
4
题型
6
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
题目相当于在一个 $10^6 \times 10^6$ 的网格中，给定源点和目标点，以及一小部分被封锁的点，问是否可以从源点到达目标点。 由于被封锁的点数量很少，最终能封锁的区域大小不超过 $|blocked|^2 / 2$，因此，我们可以从源点和目标点出发，进行深度优先搜索，直到搜索到目标点或者搜索到的点数超过 $|blocked|^2 / 2$，如果都满足，则返回 。否则返回 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
在一个 106 x 106 的网格中，每个网格上方格的坐标为 (x, y) 。
现在从源方格 source = [sx, sy] 开始出发，意图赶往目标方格 target = [tx, ty] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [xi, yi] 表示坐标为 (xi, yi) 的方格是禁止通行的。
每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格 不 在给出的封锁列表 blocked 上。同时，不允许走出网格。
只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 true。否则，返回 false。
示例 1：
输入：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2] 输出：false 解释： 从源方格无法到达目标方格，因为我们无法在网格中移动。 无法向北或者向东移动是因为方格禁止通行。 无法向南或者向西移动是因为不能走出网格。
示例 2：
输入：blocked = [], source = [0,0], target = [999999,999999] 输出：true 解释： 因为没有方格被封锁，所以一定可以到达目标方格。
提示：
0 <= blocked.length <= 200blocked[i].length == 20 <= xi, yi < 106source.length == target.length == 20 <= sx, sy, tx, ty < 106source != target- 题目数据保证
source和target不在封锁列表内
解题思路
方法一：DFS
题目相当于在一个 的网格中，给定源点和目标点，以及一小部分被封锁的点，问是否可以从源点到达目标点。
由于被封锁的点数量很少，最终能封锁的区域大小不超过 ，因此，我们可以从源点和目标点出发，进行深度优先搜索，直到搜索到目标点或者搜索到的点数超过 ，如果都满足，则返回 。否则返回 。
时间复杂度 ，空间复杂度 ，其中 是被封锁的区域的大小，本题中 。
class Solution:
def isEscapePossible(
self, blocked: List[List[int]], source: List[int], target: List[int]
) -> bool:
def dfs(source: List[int], target: List[int], vis: set) -> bool:
vis.add(tuple(source))
if len(vis) > m:
return True
for a, b in pairwise(dirs):
x, y = source[0] + a, source[1] + b
if 0 <= x < n and 0 <= y < n and (x, y) not in s and (x, y) not in vis:
if [x, y] == target or dfs([x, y], target, vis):
return True
return False
s = {(x, y) for x, y in blocked}
dirs = (-1, 0, 1, 0, -1)
n = 10**6
m = len(blocked) ** 2 // 2
return dfs(source, target, set()) and dfs(target, source, set())
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depend on the approach used. BFS typically has O(V + E) complexity where V is the number of squares and E is the number of edges (possible moves). Space complexity is proportional to the number of visited squares, which may also be O(V). With hash set optimizations, the time complexity for blocked square lookups can be reduced to O(1). |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate effectively handles blocked squares with hash lookups.
- question_mark
The candidate avoids revisiting squares and correctly uses BFS/DFS to explore the grid.
- question_mark
The candidate efficiently manages edge cases, such as blocked loops around the source or target.
常见陷阱
外企场景- error
Failing to account for the case where a path is blocked by surrounding obstacles, causing unnecessary loops.
- error
Inefficient space or time usage, especially when the grid is large, leading to excessive memory consumption or slow performance.
- error
Incorrectly assuming the target is unreachable due to insufficient exploration or misunderstanding of the BFS/DFS traversal method.
进阶变体
外企场景- arrow_right_alt
Implementing an optimized DFS that only explores viable paths to avoid excessive backtracking.
- arrow_right_alt
Using BFS with a priority queue to prioritize movement in certain directions.
- arrow_right_alt
Solving the problem by implementing a dynamic programming approach that considers each possible move.