We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Escape a Large Maze

Number: 1106

Difficulty: Hard

Paid? No

Companies: Google, Amazon, UiPath

Problem Description

Given a 1,000,000 x 1,000,000 grid, you are provided with a list of blocked cells, a source cell, and a target cell. You can move north, east, south, or west from any unblocked cell (and must remain within grid boundaries). Determine whether it is possible to reach the target cell starting from the source cell.

Key Insights

  • The maximum number of blocked cells is 200, which limits the size of a potential completely enclosed region.
  • Even if the target is unreachable by direct search, if the BFS (or DFS) explores more than a calculated threshold (based on the blocked cells count), then the region is not fully enclosed.
  • Perform two BFS explorations: one starting from the source and one from the target. If neither search is trapped within a small region, then an escape/path exists.
  • Early exit in BFS if the target is reached or if the number of visited nodes exceeds the maximum possible enclosed area.

Space and Time Complexity

Time Complexity: O(B^2) in the worst case, where B is the number of blocked cells (with B ≤ 200).
Space Complexity: O(B^2) due to the storage of visited cells in the worst-case scenario.

Solution

The solution uses the Breadth-First Search (BFS) algorithm. A key observation here is that the blocked cells can only enclose a limited area. We compute a threshold (maxSteps) based on the number of blocked cells (n*(n-1)/2) to determine if the search is confined. The BFS from the source (and similarly from the target) stops in two cases: if the target is reached or if the visited area exceeds the threshold, indicating that the region is not fully enclosed by blocked cells. Running BFS from both the source and target ensures that neither is trapped inside a small banned region.

Code Solutions

from collections import deque

def isEscapePossible(blocked, source, target):
    blocked_set = {(x, y) for x, y in blocked}
    n = len(blocked)
    if n < 2:
        return True
    max_steps = n * (n - 1) // 2
    
    def bfs(start, finish):
        queue = deque([start])
        seen = {tuple(start)}
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        steps = 0
        
        while queue:
            x, y = queue.popleft()
            if [x, y] == finish:
                return True
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < 10**6 and 0 <= ny < 10**6 and (nx, ny) not in blocked_set and (nx, ny) not in seen:
                    queue.append((nx, ny))
                    seen.add((nx, ny))
                    steps += 1
                    if steps > max_steps:
                        return True
        return False

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

# Example usage:
print(isEscapePossible([[0,1],[1,0]], [0,0], [0,2]))   # Expected output: false
print(isEscapePossible([], [0,0], [999999,999999]))      # Expected output: true
← Back to All Questions