LC 1036

Solution to LeetCode 1036 Escape A Large Maze.

LeetCode 1036

Escape A Large Maze (Hard). [link]

BFS. The key idea is instead of BFS the whole grid (10^6 * 10^6) to find a path from source to target, we BFS to find the target in the blocked sub-grid (only 200 blocks). Time complexity O(n^2), space complexity O(n^2).

class Solution(object):
    def isEscapePossible(self, blocked, source, target):
        """
        :type blocked: List[List[int]]
        :type source: List[int]
        :type target: List[int]
        :rtype: bool
        """
        BLOCKED, VALID, FOUND = -1, 0, 1
        BOUND = 10**6
        if len(blocked) < 2:
            return True
        
        hash_blocked = set(tuple(pos) for pos in blocked)
        
        def check(start, end):
            sx, sy = start
            ex, ey = end
            countdown = len(blocked) * (len(blocked) - 1) // 2
            
            q = deque([(sx, sy)]) # use queue to store next steps
            visited = set([(sx, sy)]) # use set to store visited pos
            print(visited)
            while q and countdown > 0:
                x, y = q.popleft() 
                for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
                    if 0 <= nx < BOUND and 0 <= ny <= BOUND and (nx,ny) not in hash_blocked and (nx,ny) not in visited:
                        if (nx, ny) == (ex, ey):
                            return FOUND
                        countdown -= 1
                        q.append((nx, ny))
                        visited.add((nx, ny))
            if countdown > 0: return BLOCKED
            return VALID
        
        result = check(source, target) # whether source is in the sub-grid
        if result == FOUND:
            return True
        elif result == BLOCKED:
            return False

        result = check(target, source) # whether target is in the sub-grid
        if result == BLOCKED:
            return False
        else:
            return True