Escape a Large Maze

hard graph bfs grid

Problem

There is a 10⁶ × 10⁶ grid. Some cells are blocked, given as a list blocked. Starting at source you may step to an adjacent free cell (up/down/left/right) staying inside the grid. Return true if you can reach target. The grid is enormous, but blocked has at most ~200 cells, so the only way blocked cells can stop you is by walling off a small region. If a search from a point can reach more than k·(k−1)/2 cells (where k = blocked.length), it has escaped any wall the blocked cells could build.

Inputblocked = [[0,1],[1,0]], source = [0,0], target = [0,2]

Outputfalse

The two blocked cells trap source in the corner, so its bounded BFS exhausts every reachable cell without escaping. (On a tiny demo grid, with a generous bound that means it fills its whole pocket.)

blocked (e.g. 0,1; 1,0)

source (r,c)

target (r,c)

grid size

def isEscapePossible(blocked, source, target):
    N = 10**6
    block = {(r, c) for r, c in blocked}
    limit = len(blocked) * (len(blocked) - 1) // 2

    def bfs(sx, sy, tx, ty):
        seen = {(sx, sy)}
        q = [(sx, sy)]
        while q:
            x, y = q.pop()
            if (x, y) == (tx, ty):
                return True
            if len(seen) > limit:
                return True
            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nx, ny = x + dx, y + dy
                if 0 <= nx < N and 0 <= ny < N \
                        and (nx, ny) not in block and (nx, ny) not in seen:
                    seen.add((nx, ny))
                    q.append((nx, ny))
        return False

    return bfs(*source, *target) and bfs(*target, *source)

function isEscapePossible(blocked, source, target) {
  const N = 1e6;
  const block = new Set(blocked.map(([r, c]) => r + "," + c));
  const limit = (blocked.length * (blocked.length - 1)) / 2;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  function bfs(sx, sy, tx, ty) {
    const seen = new Set([sx + "," + sy]);
    const q = [[sx, sy]];
    while (q.length) {
      const [x, y] = q.pop();
      if (x === tx && y === ty) return true;
      if (seen.size > limit) return true;
      for (const [dx, dy] of dirs) {
        const nx = x + dx, ny = y + dy, key = nx + "," + ny;
        if (nx >= 0 && nx < N && ny >= 0 && ny < N
            && !block.has(key) && !seen.has(key)) {
          seen.add(key);
          q.push([nx, ny]);
        }
      }
    }
    return false;
  }

  return bfs(...source, ...target) && bfs(...target, ...source);
}

class Solution {
    static final int N = 1_000_000;
    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        Set<Long> block = new HashSet<>();
        for (int[] b : blocked) block.add((long) b[0] * N + b[1]);
        long limit = (long) blocked.length * (blocked.length - 1) / 2;
        return bfs(block, limit, source, target) && bfs(block, limit, target, source);
    }
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    boolean bfs(Set<Long> block, long limit, int[] s, int[] t) {
        Set<Long> seen = new HashSet<>();
        Deque<int[]> q = new ArrayDeque<>();
        q.push(s); seen.add((long) s[0] * N + s[1]);
        while (!q.isEmpty()) {
            int[] cur = q.pop();
            if (cur[0] == t[0] && cur[1] == t[1]) return true;
            if (seen.size() > limit) return true;
            for (int[] d : dirs) {
                int nx = cur[0] + d[0], ny = cur[1] + d[1];
                long key = (long) nx * N + ny;
                if (nx >= 0 && nx < N && ny >= 0 && ny < N
                        && !block.contains(key) && !seen.contains(key)) {
                    seen.add(key);
                    q.push(new int[]{nx, ny});
                }
            }
        }
        return false;
    }
}

class Solution {
    static const int N = 1000000;
    vector<vector<int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    bool bfs(unordered_set<long>& block, long limit, vector<int>& s, vector<int>& t) {
        unordered_set<long> seen;
        vector<pair<int,int>> q = {{s[0], s[1]}};
        seen.insert((long)s[0] * N + s[1]);
        while (!q.empty()) {
            auto [x, y] = q.back(); q.pop_back();
            if (x == t[0] && y == t[1]) return true;
            if ((long)seen.size() > limit) return true;
            for (auto& d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                long key = (long)nx * N + ny;
                if (nx >= 0 && nx < N && ny >= 0 && ny < N
                        && !block.count(key) && !seen.count(key)) {
                    seen.insert(key);
                    q.push_back({nx, ny});
                }
            }
        }
        return false;
    }
public:
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        unordered_set<long> block;
        for (auto& b : blocked) block.insert((long)b[0] * N + b[1]);
        long limit = (long)blocked.size() * (blocked.size() - 1) / 2;
        return bfs(block, limit, source, target) && bfs(block, limit, target, source);
    }
};

Explanation

The grid is a million by a million, so we can never flood-fill the whole thing. The clever insight is that only a small set of blocked cells can stop you, and they can only do that by building a tiny wall that traps you in a small pocket.

So we run a bounded BFS with a cap. If k = blocked.length, the most cells the blocked set can ever wall off is about k·(k-1)/2. If our BFS reaches more cells than that limit, we have clearly broken out into open space and can stop early returning success.

The BFS either reaches the target directly (return true), or expands past the limit (escaped, return true), or runs out of cells first (trapped, return false). We do this twice — once from source toward target, once from target toward source — because a wall could trap either endpoint. Both must escape or connect.

Example: blocked=[[0,1],[1,0]], source=[0,0], target=[0,2]. The two blocked cells fence the source into the corner. Its BFS exhausts the tiny pocket without escaping or reaching the target, so the answer is false.

Because the search stops as soon as it sees more than limit cells, each BFS does only O(k²) work no matter how vast the real grid is.

Time: O(k²) Space: O(k²)