# 1036. Escape a Large Maze

In a 1 million by 1 million grid, the coordinates of each grid square are (x, y) with 0 <= x, y < 10^6.

We start at the source square and want to reach the target square. Each move, we can walk to a 4-directionally adjacent square in the grid that isn't in the given list of blocked squares. Note that 0 <= blocked.length <= 200.

Return true if and only if it is possible to reach the target square through a sequence of moves.

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 can't walk outside the grid.

Example 2:

Input: blocked = [], source = [0,0], target = [999999,999999]
Output: true
Explanation: 
Because there are no blocked cells, it's possible to reach the target square.

# Solution

Approach 1: since there are at most 200 blocker squares (0 <= blocked.length <= 200), we search 200 steps at most and see we can still move around.

# Code (Python)

Approach 1:

class Solution(object):
    def isEscapePossible(self, blocked, source, target):
        """
        :type blocked: List[List[int]]
        :type source: List[int]
        :type target: List[int]
        :rtype: bool
        """
        # idea: since there are at most 200 blocker squares (0 <= blocked.length <= 200), we search 200 steps at most and see we can still move around.
        if len(blocked) <= 1:
            return True
        blocked = set(map(tuple, blocked))
        return self._can_escape(source, blocked, len(blocked)) and self._can_escape(target, blocked, len(blocked)) 
    
    def _can_escape(self, start, blockers, max_steps):
        queue = collections.deque([start])
        visited = set(tuple(start))
        steps = 0
        while queue:
            for _ in range(len(queue)):
                square = queue.popleft()
                for delta in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    neighbor = (square[0] + delta[0], square[1] + delta[1])
                    if 0 <= neighbor[0] < 10**6 and 0 <= neighbor[1] < 10**6 and neighbor not in visited and neighbor not in blockers:
                        queue.append(neighbor)
                        visited.add(neighbor)
            steps += 1
            if steps == max_steps:
                break
        return queue and steps == max_steps

# Code (C++)

Approach 1:

Approach 2: