HardNo. 1036
Escape a Large Maze — LeetCode 1036 Python Solution
- Pattern
- Breadth-First Search
- Topics
- Depth-First Search, Breadth-First Search, Array, Hash Table
- Reading time
- 4 min
- Source
- leetcode.com
The problem
There is a 1 million by 1 million grid on an XY-plane, and the coordinates of each grid square are (x, y). We start at the source = [sx, sy] square and want to reach the target = [tx, ty] square.
Example
- Input
- blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
- Output
- false
- Explanation
- The target square is inaccessible starting from the source square because we cannot move.
Python solution
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())Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Breadth-First Search
Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 1036. Escape a Large Maze is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.
The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0690 | Employee Importance | Medium |
| 0721 | Accounts Merge | Medium |
| 0839 | Similar String Groups | Hard |
| 0924 | Minimize Malware Spread | Hard |
| 0928 | Minimize Malware Spread II | Hard |
| 0959 | Regions Cut By Slashes | Medium |
Frequently asked questions
- How hard is LeetCode 1036. Escape a Large Maze?
LeetCode 1036. Escape a Large Maze is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1036. Escape a Large Maze?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1036. Escape a Large Maze?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1036. Escape a Large Maze cover?
LeetCode 1036. Escape a Large Maze is tagged Depth-First Search, Breadth-First Search, Array and Hash Table on LeetCode.