# 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: