# 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.
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.
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.
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)
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 + delta, square + delta) if 0 <= neighbor < 10**6 and 0 <= neighbor < 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++)