# Escape a Large Maze
**Difficulty:** HARD
[External](https://leetcode.com/problems/escape-a-large-maze)
Canonical: https://scaleengineer.com/dsa/problems/escape-a-large-maze
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Hash Table
**Companies:** [UiPath](https://scaleengineer.com/companies/uipath)
---
## 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 the_ `target` _square from the_ `source` _square through a sequence of valid 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 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:**

**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 < 106`
* `source.length == target.length == 2`
* `0 <= sx, sy, tx, ty < 106`
* `source != target`
* It is guaranteed that `source` and `target` are not blocked.

# Approaches
## Brute Force BFS/DFS
A straightforward but impractical approach is to model the entire 10^6 x 10^6 grid as a graph and perform a standard traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS). We would start at the `source` and explore adjacent cells, keeping track of visited cells to avoid cycles, until we either find the `target` or exhaust all reachable cells.
**Time:** O(N*M) in the worst case, where N and M are the grid dimensions. This is far too slow for the given constraints. · **Space:** O(N*M), where N and M are the dimensions of the grid (10^6 x 10^6). This is required for the `visited` set and is prohibitively large.
**Pros:** Conceptually simple and easy to understand.
**Cons:** **Memory Limit Exceeded:** The `visited` set could potentially store up to 10^12 coordinates, which is far beyond the memory capacity of any typical competitive programming environment.; **Time Limit Exceeded:** The search space is enormous. In an open grid, the search would explore a vast number of cells before reaching a distant target, leading to a timeout.
### Explanation
This method directly translates the problem into a graph traversal problem without considering the specific constraints. The grid cells are the nodes, and valid moves between adjacent cells are the edges. A standard BFS would guarantee finding the shortest path if one exists, but we only need to determine existence. However, the sheer size of the grid makes this approach infeasible. The number of cells is 10^12, so any algorithm that attempts to visit a significant fraction of the grid or store their visited status will fail due to time and memory constraints.
### Algorithm
1. Treat the 10^6 x 10^6 grid as a graph.
2. Start a Breadth-First Search (BFS) or Depth-First Search (DFS) from the `source` coordinate.
3. Use a queue (for BFS) or stack (for DFS) to manage coordinates to visit.
4. Use a large hash set to keep track of `visited` coordinates to avoid cycles and redundant computations.
5. In each step, explore the four neighbors (north, east, south, west).
6. If a neighbor is within the grid boundaries, not blocked, and not visited, add it to the queue/stack and the visited set.
7. Continue the search until the `target` coordinate is found (return `true`) or the queue/stack becomes empty (return `false`).

## Bounded Breadth-First Search
This approach leverages the crucial constraint that the number of blocked cells is very small (`<= 200`). These few blocks can only cordon off a finite, limited area. If the source is not trapped within such an area, it can access the vast, open parts of the grid. The same applies to the target. If both the source and target can reach this "open space," they can surely reach each other.

We can quantify the maximum possible area that can be enclosed. With `B` blocks, the largest area you can enclose is less than `B*B / 2`. We use this as a threshold. We perform a Breadth-First Search (BFS) from the `source`. If the search explores more cells than this threshold, we know the `source` isn't trapped. We do the same for the `target`. If both are not trapped, a path exists. This check also handles the case where the `source` and `target` are close and in the same enclosed region, as the BFS from `source` would find `target` directly.
**Time:** O(B^2), where B is the number of blocked cells. We perform two BFS runs, and each search explores at most `O(B^2)` cells. Creating the initial `blockedSet` takes O(B). · **Space:** O(B^2), where B is the number of blocked cells. The `visited` set and the BFS `queue` will store at most `O(B^2)` elements in the worst case for each of the two BFS runs.
**Pros:** **Highly Efficient:** Avoids exploring the entire grid by limiting the search space based on the number of blocks.; **Correctness:** The logic correctly handles all cases, including when source/target are trapped or in open space.; **Optimal Complexity:** The time and space complexity are polynomial in the number of blocks, not the grid size, making it feasible.
**Cons:** The logic of needing two separate checks (`source` to `target` and `target` to `source`) might not be immediately intuitive.; Requires careful handling of large coordinates to use as keys in hash sets (e.g., converting `(x, y)` to a single `long`).
### Explanation
The algorithm is implemented by creating a helper function, `bfs(start, end, blockedSet, limit)`, which performs a bounded search. This function returns `true` if it either reaches `end` or if the number of visited cells surpasses the `limit`. It returns `false` if the reachable area from `start` is exhausted and is smaller than the `limit` and does not contain `end`.

The main function then calls this helper twice: `bfs(source, target, ...)` and `bfs(target, source, ...)`. Both must be `true` for a path to be guaranteed. This correctly handles all scenarios:
- **Source and Target in the same small region:** The first call finds the target and returns `true`. The second call finds the source and returns `true`. Result: `true`.
- **Source trapped, Target in open space:** The first call returns `false`. Result: `false`.
- **Source and Target in different trapped regions:** The first call returns `false`. Result: `false`.
- **Source and Target in open space:** Both calls return `true` because their search areas will exceed the limit. Result: `true`.

To handle the large coordinates efficiently, we convert each `(x, y)` pair into a single `long` value (`key = x * 10^6 + y`) for use in `HashSet`s.

```java
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution {
    private static final long GRID_SIZE = 1_000_000L;
    private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        Set<Long> blockedSet = new HashSet<>();
        for (int[] block : blocked) {
            blockedSet.add((long)block[0] * GRID_SIZE + block[1]);
        }

        // With B blocks, the maximum area they can enclose is B*(B-1)/2.
        // If we visit more than this number of cells, we have escaped the enclosure.
        int limit = blocked.length * (blocked.length - 1) / 2;

        return bfs(source, target, blockedSet, limit) && bfs(target, source, blockedSet, limit);
    }

    private boolean bfs(int[] start, int[] end, Set<Long> blockedSet, int limit) {
        Queue<int[]> queue = new LinkedList<>();
        Set<Long> visited = new HashSet<>();
        
        long startKey = (long)start[0] * GRID_SIZE + start[1];
        long endKey = (long)end[0] * GRID_SIZE + end[1];

        queue.offer(start);
        visited.add(startKey);

        while (!queue.isEmpty()) {
            // If the number of visited cells exceeds the limit, we have escaped.
            if (visited.size() > limit) {
                return true;
            }

            int[] current = queue.poll();

            if ((long)current[0] * GRID_SIZE + current[1] == endKey) {
                return true;
            }

            for (int[] dir : dirs) {
                int nextX = current[0] + dir[0];
                int nextY = current[1] + dir[1];
                long nextKey = (long)nextX * GRID_SIZE + nextY;

                if (nextX >= 0 && nextX < GRID_SIZE &&
                    nextY >= 0 && nextY < GRID_SIZE &&
                    !blockedSet.contains(nextKey) &&
                    visited.add(nextKey)) { // .add() returns true if the element was new
                    
                    queue.offer(new int[]{nextX, nextY});
                }
            }
        }
        
        // If the queue is empty, we are trapped in a small area.
        return false;
    }
}
```
### Algorithm
1. **Key Insight:** A small number of blocks (`B` <= 200) can only enclose a relatively small area. The maximum area that `B` blocks can trap is `B * (B - 1) / 2`. For `B=200`, this is `19900` cells.
2. **Strategy:** If a point (source or target) can reach more cells than this maximum trappable area, it must be in an open region and can be considered to have "escaped". If both source and target can escape, they can reach each other through the vast open grid.
3. **Implementation:** We run two separate, bounded BFS searches:
    a. One from `source` to `target`.
    b. One from `target` to `source`.
4. **Bounded BFS Logic (`bfs(start, end)`):**
    a. Store blocked cells in a `HashSet` for O(1) lookups.
    b. Initialize a queue for BFS and a `visited` set.
    c. Set a `limit` for the search area, e.g., `limit = blocked.length * (blocked.length - 1) / 2`.
    d. Begin BFS from `start`.
    e. In the BFS loop, if `visited.size()` exceeds the `limit`, it means `start` has escaped. Return `true`.
    f. If the `end` point is found, a path exists. Return `true`.
    g. If the queue becomes empty before either of the above conditions is met, it means `start` is trapped in a small area that doesn't contain `end`. Return `false`.
5. **Final Result:** The function returns `true` only if both `bfs(source, target)` AND `bfs(target, source)` return `true`. This covers all cases: both are in a large open area, or both are in the same small enclosed area.

# Solutions
### Java

```java
class Solution {
private
  int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private
  static final int N = (int)1 e6;
private
  Set<Integer> blocked;
public
  boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
    this.blocked = new HashSet<>();
    for (int[] b : blocked) {
      this.blocked.add(b[0] * N + b[1]);
    }
    return dfs(source, target, new HashSet<>()) &&
           dfs(target, source, new HashSet<>());
  }
private
  boolean dfs(int[] source, int[] target, Set<Integer> seen) {
    int sx = source[0], sy = source[1];
    int tx = target[0], ty = target[1];
    if (sx < 0 || sx >= N || sy < 0 || sy >= N || tx < 0 || tx >= N || ty < 0 ||
        ty >= N || blocked.contains(sx * N + sy) ||
        seen.contains(sx * N + sy)) {
      return false;
    }
    seen.add(sx * N + sy);
    if (seen.size() > 20000 || (sx == target[0] && sy == target[1])) {
      return true;
    }
    for (int[] dir : dirs) {
      if (dfs(new int[]{sx + dir[0], sy + dir[1]}, target, seen)) {
        return true;
      }
    }
    return false;
  }
}

```

### CPP

```cpp
typedef unsigned long long ULL ; class Solution { public: vector < vector < int >> dirs = { { 0 , 1 }, { 0 , - 1 }, { 1 , 0 }, { - 1 , 0 } }; unordered_set < ULL > blocked ; int N = 1e6 ; bool isEscapePossible ( vector < vector < int >>& blocked , vector < int >& source , vector < int >& target ) { this -> blocked . clear (); for ( auto & b : blocked ) this -> blocked . insert (( ULL ) b [ 0 ] * N + b [ 1 ]); unordered_set < ULL > s1 ; unordered_set < ULL > s2 ; return dfs ( source , target , s1 ) && dfs ( target , source , s2 ); } bool dfs ( vector < int >& source , vector < int >& target , unordered_set < ULL >& seen ) { int sx = source [ 0 ], sy = source [ 1 ]; int tx = target [ 0 ], ty = target [ 1 ]; if ( sx < 0 || sx >= N || sy < 0 || sy >= N || tx < 0 || tx >= N || ty < 0 || ty >= N || blocked . count (( ULL ) sx * N + sy ) || seen . count (( ULL ) sx * N + sy )) return 0 ; seen . insert (( ULL ) sx * N + sy ); if ( seen . size () > 20000 || ( sx == target [ 0 ] && sy == target [ 1 ])) return 1 ; for ( auto & dir : dirs ) { vector < int > next = { sx + dir [ 0 ], sy + dir [ 1 ]}; if ( dfs ( next , target , seen )) return 1 ; } return 0 ; } };
```

### Python

```python
class Solution:
    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool: def dfs(source, target, seen): x, y = source if (not (0 <= x < 10 ** 6 and 0 <= y < 10 ** 6) or (x, y) in blocked or (x, y) in seen): return False seen . add((x, y)) if len(seen) > 20000 or source == target: return True for a, b in [[0, - 1], [0, 1], [1, 0], [- 1, 0]]: next = [x + a, y + b] if dfs(next, target, seen): return True return False blocked = set((x, y) for x, y in blocked) return dfs(source, target, set()) and dfs(target, source, set())

```