#1036

Escape a Large Maze

master · 1825 · lc hard +32 · verified · 36.4% accepted · 712 likes · top 14%

⚑ DFS / BFS: Connected Components & Reachability

Description

On a 10⁶ x 10⁶ grid, starting from source, determine whether target is reachable by moving one step north, south, east, or west at a time while avoiding the cells in blocked and staying within the grid.

Return true if and only if target is reachable.

Example 1:

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.

We cannot move north or east because those squares are blocked.

We cannot move south or west because we cannot go outside of the grid.

Example 2:

Input: blocked = [], source = [0,0], target = [999999,999999]

Output: true

Explanation: Because there are no blocked cells, it is possible to reach the target square.

Code

1

2

3

class Solution:
    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:

class Solution:
    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool: