Escape a Large Maze

Problem

There is a 1 million by 1 million grid on an XY-plane, and the coordinates of each grid square are (x, y).

We start at the source = [sx, sy] square and want to reach the target = [tx, ty] square. There is also an array of blocked squares, where each blocked[i] = [xi, yi] represents a blocked square with coordinates (xi, yi).

Each move, we can walk one square north, east, south, or west if the square is not in the array of blocked squares. We are also not allowed to walk outside of the grid.

Return true if and only if it is possible to reach thetarget square from thesource square through a sequence of valid moves.

Examples

Example 1

1
2
3
4
5


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 cannot move.
We cannot move north or east because those squares are blocked.
We cannot move south or west because we cannot go outside of the grid.

Example 2

1
2
3


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

Constraints

0 <= blocked.length <= 200
blocked[i].length == 2
0 <= xi, yi < 10^6
source.length == target.length == 2
0 <= sx, sy, tx, ty < 10^6
source != target
It is guaranteed that source and target are not blocked.

Solution

Method 1 – Bounded BFS with Blocked Area Limit

Intuition

Since the number of blocked cells is small (at most 200), the maximum area they can enclose is limited. If we can escape from the source (or target) to more than this area, then the path is not blocked. We use BFS from both source and target, and if both can reach more than the maximum possible blocked area, escape is possible.

Approach

Let blocked be a set of blocked cells. The maximum area that can be enclosed is len(blocked) * (len(blocked) - 1) // 2.
Use BFS from source and target separately, each time stopping if we reach the other or if we visit more than the maximum area.
If both BFS can reach more than the maximum area, return True. Otherwise, return False.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution {
public:
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        unordered_set<long long> block;
        for (auto& b : blocked) block.insert((long long)b[0] << 20 | b[1]);
        int max_area = blocked.size() * (blocked.size() - 1) / 2;
        auto bfs = [&](vector<int>& start, vector<int>& end) {
            unordered_set<long long> vis;
            queue<pair<int,int>> q;
            q.push({start[0], start[1]});
            vis.insert(((long long)start[0] << 20) | start[1]);
            int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
            while (!q.empty() && vis.size() <= max_area) {
                auto [x, y] = q.front(); q.pop();
                if (x == end[0] && y == end[1]) return true;
                for (auto& d : dirs) {
                    int nx = x + d[0], ny = y + d[1];
                    if (nx < 0 || ny < 0 || nx >= 1e6 || ny >= 1e6) continue;
                    long long key = ((long long)nx << 20) | ny;
                    if (block.count(key) || vis.count(key)) continue;
                    vis.insert(key);
                    q.push({nx, ny});
                }
            }
            return vis.size() > max_area;
        };
        return bfs(source, target) && bfs(target, source);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution {
    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        Set<Long> block = new HashSet<>();
        for (int[] b : blocked) block.add(((long)b[0] << 20) | b[1]);
        int maxArea = blocked.length * (blocked.length - 1) / 2;
        return bfs(source, target, block, maxArea) && bfs(target, source, block, maxArea);
    }
    private boolean bfs(int[] start, int[] end, Set<Long> block, int maxArea) {
        Set<Long> vis = new HashSet<>();
        Queue<int[]> q = new LinkedList<>();
        q.offer(start);
        vis.add(((long)start[0] << 20) | start[1]);
        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
        while (!q.isEmpty() && vis.size() <= maxArea) {
            int[] cur = q.poll();
            if (cur[0] == end[0] && cur[1] == end[1]) return true;
            for (int[] d : dirs) {
                int nx = cur[0] + d[0], ny = cur[1] + d[1];
                if (nx < 0 || ny < 0 || nx >= 1e6 || ny >= 1e6) continue;
                long key = ((long)nx << 20) | ny;
                if (block.contains(key) || vis.contains(key)) continue;
                vis.add(key);
                q.offer(new int[]{nx, ny});
            }
        }
        return vis.size() > maxArea;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
    def isEscapePossible(self, blocked: list[list[int]], source: list[int], target: list[int]) -> bool:
        blocked_set = {tuple(b) for b in blocked}
        max_area = len(blocked) * (len(blocked) - 1) // 2
        def bfs(start, end):
            vis = set()
            q = [tuple(start)]
            vis.add(tuple(start))
            dirs = [(0,1),(1,0),(0,-1),(-1,0)]
            while q and len(vis) <= max_area:
                x, y = q.pop(0)
                if [x, y] == end:
                    return True
                for dx, dy in dirs:
                    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 vis:
                        vis.add((nx, ny))
                        q.append((nx, ny))
            return len(vis) > max_area
        return bfs(source, target) and bfs(target, source)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


use std::collections::{HashSet, VecDeque};
impl Solution {
    pub fn is_escape_possible(blocked: Vec<Vec<i32>>, source: Vec<i32>, target: Vec<i32>) -> bool {
        let block: HashSet<(i32, i32)> = blocked.iter().map(|b| (b[0], b[1])).collect();
        let max_area = blocked.len() * (blocked.len() - 1) / 2;
        fn bfs(start: &[i32], end: &[i32], block: &HashSet<(i32, i32)>, max_area: usize) -> bool {
            let mut vis = HashSet::new();
            let mut q = VecDeque::new();
            q.push_back((start[0], start[1]));
            vis.insert((start[0], start[1]));
            let dirs = [(0,1),(1,0),(0,-1),(-1,0)];
            while let Some((x, y)) = q.pop_front() {
                if vis.len() > max_area { return true; }
                if [x, y] == [end[0], end[1]] { return true; }
                for (dx, dy) in dirs.iter() {
                    let nx = x + dx;
                    let ny = y + dy;
                    if nx < 0 || ny < 0 || nx >= 1_000_000 || ny >= 1_000_000 { continue; }
                    if block.contains(&(nx, ny)) || vis.contains(&(nx, ny)) { continue; }
                    vis.insert((nx, ny));
                    q.push_back((nx, ny));
                }
            }
            vis.len() > max_area
        }
        bfs(&source, &target, &block, max_area) && bfs(&target, &source, &block, max_area)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
    isEscapePossible(blocked: number[][], source: number[], target: number[]): boolean {
        const block = new Set(blocked.map(([x, y]) => x + ',' + y));
        const maxArea = blocked.length * (blocked.length - 1) / 2;
        const bfs = (start: number[], end: number[]): boolean => {
            const vis = new Set<string>();
            const q: number[][] = [start];
            vis.add(start.join(','));
            const dirs = [[0,1],[1,0],[0,-1],[-1,0]];
            while (q.length && vis.size <= maxArea) {
                const [x, y] = q.shift()!;
                if (x === end[0] && y === end[1]) return true;
                for (const [dx, dy] of dirs) {
                    const nx = x + dx, ny = y + dy;
                    const key = nx + ',' + ny;
                    if (nx < 0 || ny < 0 || nx >= 1e6 || ny >= 1e6) continue;
                    if (block.has(key) || vis.has(key)) continue;
                    vis.add(key);
                    q.push([nx, ny]);
                }
            }
            return vis.size > maxArea;
        };
        return bfs(source, target) && bfs(target, source);
    }
}

Complexity

⏰ Time complexity: O(B^2) where B is the number of blocked cells (since the area that can be blocked is limited).
🧺 Space complexity: O(B^2) for visited sets.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Bounded BFS with Blocked Area Limit#

Intuition#

Approach#

Code#

Complexity#