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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Escape a Large Maze

Difficulty: Hard

Problem Description

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 = [s_x, s_y] square and want to reach the target = [t_x, t_y] square. There is also an array of blocked squares, where each blocked[i] = [x_i, y_i] represents a blocked square with coordinates (x_i, y_i). Each move, we can walk one square north, east, south, or west if the square is not in the array of blocked squares. We are also not allowed to walk outside of the grid. Return true if and only if it is possible to reach the target square from the source square through a sequence of valid moves.

Key Insights

  • The grid is extremely large (1,000,000 x 1,000,000), making it impractical to represent the entire grid in memory.
  • The number of blocked squares is limited (up to 200), which allows for a more efficient search.
  • A breadth-first search (BFS) or depth-first search (DFS) can be used to explore reachable squares from the source.
  • The position of the target relative to the source and the blocked squares can determine the path's feasibility.

Space and Time Complexity

Time Complexity: O(B) where B is the number of blocked squares, as we may need to check each blocked square during the search. Space Complexity: O(B) for storing the blocked squares and the visited set during the search.

Solution

To solve the problem, we can use a breadth-first search (BFS) approach. We will maintain a queue to explore each square starting from the source. We also maintain a set of blocked squares for quick lookup. The BFS will explore all possible moves (north, south, east, west) from the current position, checking if the move is valid (not blocked and within the grid bounds). If we reach the target during the process, we return true. If the queue is exhausted without reaching the target, we return false.

Code Solutions

from collections import deque

def isEscapePossible(blocked, source, target):
    if not blocked:
        return True
    
    blocked_set = set(map(tuple, blocked))
    return bfs(source, target, blocked_set) and bfs(target, source, blocked_set)

def bfs(start, end, blocked_set):
    queue = deque([start])
    visited = set([tuple(start)])
    
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    while queue:
        x, y = queue.popleft()
        
        if abs(x - end[0]) + abs(y - end[1]) <= 200:  # Check if we can reach end directly
            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 visited:
                visited.add((nx, ny))
                queue.append((nx, ny))
    
    return False
← Back to All Questions