The "Escape a Large Maze" problem asks you to determine whether it is possible to move from a given source cell to a target cell in a very large grid (1,000,000 x 1,000,000), given a list of blocked cells that cannot be entered.
Key constraints:
source to target without passing through blocked cells.blocked (List[List[int]]): List of blocked cell coordinatessource (List[int]): Starting cell coordinatestarget (List[int]): Destination cell coordinatesTrue if escape is possible, otherwise False.
At first glance, you might think to use a standard breadth-first or depth-first search to explore all possible paths from the source to the target. However, since the grid is so large (1,000,000 x 1,000,000), it is impossible to visit every cell or even to build the entire grid in memory.
The next idea is to only consider the blocked cells, since there are so few (at most 200). The challenge becomes: could these blocked cells form a "wall" that traps the source or target in a small enclosed area? Or, if not, can you always escape?
This leads to the insight that, with so few blocked cells, the only way escape is impossible is if the source (or target) is completely surrounded by blocked cells. Otherwise, there will always be a way to reach the target by going around the blocked area.
We need an efficient way to determine if the source or target is enclosed by blocked cells. Here's a step-by-step breakdown:
source and the target, but only up to a certain number of steps.
n blocked cells is n * (n - 1) / 2. So, if you can reach more than this number of unique cells from your starting point, you know you are not trapped.
source and target to ensure neither is trapped in a blocked enclosure.
target), return True. Otherwise, return False.
source or target is surrounded by blocked cells.
Example:
blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Let's walk through the steps:
source is at (0,0).
source is completely surrounded and cannot move.
source will visit only (0,0). Since it can't reach enough cells, we return False.
blocked = [[0,1],[1,2],[2,1]], source = [0,0], target = [3,3]
source will quickly visit more than the maximum possible enclosed area, and so escape is possible.
Brute-force approach:
Attempting to search the entire grid would take O(N^2) time and space, which is infeasible for N = 1,000,000.
Optimized approach:
max_area = n*(n-1)//2 nodes, where n is the number of blocked cells (at most 200).
source and target.
The "Escape a Large Maze" problem leverages the insight that, with very few blocked cells, it is only possible to be trapped if you are fully enclosed. By limiting BFS to the maximum area that can possibly be blocked off, we efficiently and safely determine if escape is possible without needing to traverse the entire grid. This approach is both elegant and practical, making use of problem constraints to avoid brute-force search.
class Solution:
def isEscapePossible(self, blocked, source, target):
blocked_set = {tuple(x) for x in blocked}
max_area = len(blocked) * (len(blocked) - 1) // 2
def bfs(start, finish):
from collections import deque
visited = set()
queue = deque()
queue.append(tuple(start))
visited.add(tuple(start))
directions = [(-1,0),(1,0),(0,-1),(0,1)]
while queue and len(visited) <= max_area:
x, y = queue.popleft()
if [x, y] == finish:
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 len(visited) > max_area
return bfs(source, target) and bfs(target, source)
class Solution {
public:
bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
unordered_set<long long> blocked_set;
int n = blocked.size();
long long max_area = (long long)n * (n - 1) / 2;
for (auto& b : blocked) {
blocked_set.insert((long long)b[0] * 1000000 + b[1]);
}
auto bfs = [&](vector<int>& start, vector<int>& finish) {
unordered_set<long long> visited;
queue<pair<int,int>> q;
q.push({start[0], start[1]});
visited.insert((long long)start[0] * 1000000 + start[1]);
vector<pair<int,int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
while (!q.empty() && visited.size() <= max_area) {
auto [x, y] = q.front(); q.pop();
if (x == finish[0] && y == finish[1]) return true;
for (auto& d : dirs) {
int nx = x + d.first, ny = y + d.second;
long long key = (long long)nx * 1000000 + ny;
if (nx >= 0 && nx < 1000000 && ny >= 0 && ny < 1000000
&& !blocked_set.count(key) && !visited.count(key)) {
visited.insert(key);
q.push({nx, ny});
}
}
}
return visited.size() > max_area;
};
return bfs(source, target) && bfs(target, source);
}
};
import java.util.*;
class Solution {
public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
Set<Long> blockedSet = new HashSet<>();
int n = blocked.length;
long maxArea = (long)n * (n - 1) / 2;
for (int[] b : blocked) {
blockedSet.add((long)b[0] * 1000000 + b[1]);
}
return bfs(source, target, blockedSet, maxArea) && bfs(target, source, blockedSet, maxArea);
}
private boolean bfs(int[] start, int[] finish, Set<Long> blockedSet, long maxArea) {
Set<Long> visited = new HashSet<>();
Queue<int[]> queue = new LinkedList<>();
queue.offer(start);
visited.add((long)start[0] * 1000000 + start[1]);
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
while (!queue.isEmpty() && visited.size() <= maxArea) {
int[] curr = queue.poll();
if (curr[0] == finish[0] && curr[1] == finish[1]) return true;
for (int[] d : dirs) {
int nx = curr[0] + d[0], ny = curr[1] + d[1];
long key = (long)nx * 1000000 + ny;
if (nx >= 0 && nx < 1000000 && ny >= 0 && ny < 1000000
&& !blockedSet.contains(key) && !visited.contains(key)) {
visited.add(key);
queue.offer(new int[]{nx, ny});
}
}
}
return visited.size() > maxArea;
}
}
var isEscapePossible = function(blocked, source, target) {
const blockedSet = new Set(blocked.map(([x, y]) => x + ',' + y));
const maxArea = blocked.length * (blocked.length - 1) / 2;
function bfs(start, finish) {
const visited = new Set();
const queue = [start];
visited.add(start.join(','));
const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
while (queue.length && visited.size <= maxArea) {
const [x, y] = queue.shift();
if (x === finish[0] && y === finish[1]) return true;
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
const key = nx + ',' + ny;
if (nx >= 0 && nx < 1e6 && ny >= 0 && ny < 1e6 &&
!blockedSet.has(key) && !visited.has(key)) {
visited.add(key);
queue.push([nx, ny]);
}
}
}
return visited.size > maxArea;
}
return bfs(source, target) && bfs(target, source);
};