LeetCode 1036: Escape a Large Maze

Problem Restatement

We have a 10^6 x 10^6 grid. Some cells are blocked.

We are given:

• blocked: list of blocked cells.
• source: starting cell.
• target: target cell.

We need to return true if source can reach target, or false if it is impossible.

The official constraints state that 0 <= blocked.length <= 200, and cells are given as [r, c].

Input and Output

Function shape:

def isEscapePossible(blocked: list[list[int]], source: list[int], target: list[int]) -> bool:
    ...

Key Insight

With at most 200 blocked cells, the maximum area they can enclose is 200 * 200 / 2 = 20000 cells (a triangle arrangement).

So if BFS from source finds more than 20000 cells without being blocked, it has escaped the enclosed region and can reach target.

Conversely, if source BFS stays within 20000 cells and target is not reached, source is enclosed.

Run BFS from both source and target. If both escape or one reaches the other, return True.

Algorithm

Define bfs(start, goal):

• BFS up to limit = len(blocked)^2 // 2 cells.
• If we reach goal or visit more than limit cells, return True.
• Otherwise return False.

Return bfs(source, target) and bfs(target, source).

Correctness

If source can visit more than limit cells without hitting the goal, it has escaped any possible enclosed region formed by the blocked cells. Similarly for target. Both must be able to escape (or find each other) for a path to exist.

Edge Cases

• Mark nodes or cells as visited at enqueue/discovery time to avoid duplicate work.
• Return the failure value when the destination is unreachable.
• Check grid or graph boundaries before reading neighbors.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from collections import deque

class Solution:
    def isEscapePossible(self, blocked: list[list[int]], source: list[int], target: list[int]) -> bool:
        if not blocked:
            return True

        blocked_set = set(map(tuple, blocked))
        limit = len(blocked) ** 2 // 2
        N = 10 ** 6

        def bfs(start, goal):
            sr, sc = start
            gr, gc = goal
            visited = {(sr, sc)}
            queue = deque([(sr, sc)])

            while queue:
                if len(visited) > limit:
                    return True
                r, c = queue.popleft()
                for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    nr, nc = r + dr, c + dc
                    if (0 <= nr < N and 0 <= nc < N
                            and (nr, nc) not in blocked_set
                            and (nr, nc) not in visited):
                        if nr == gr and nc == gc:
                            return True
                        visited.add((nr, nc))
                        queue.append((nr, nc))

            return False

        return bfs(source, target) and bfs(target, source)

Testing

def run_tests():
    s = Solution()

    assert s.isEscapePossible([], [0,0], [999999,999999]) == True
    assert s.isEscapePossible([[0,1],[1,0]], [0,0], [999999,999999]) == False
    assert s.isEscapePossible([[0,1],[1,0]], [0,0], [0,2]) == False

    print("all tests passed")

run_tests()