# LeetCode 1036: Escape a Large Maze

## Problem Restatement

We have a `10^6 x 10^6` grid. Some cells are blocked.

We are given:
- `blocked`: list of blocked cells.
- `source`: starting cell.
- `target`: target cell.

We need to return `true` if `source` can reach `target`, or `false` if it is impossible.

The official constraints state that `0 <= blocked.length <= 200`, and cells are given as `[r, c]`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `blocked` cells, `source`, `target` |
| Output | `true` if source can reach target |

Function shape:

```python
def isEscapePossible(blocked: list[list[int]], source: list[int], target: list[int]) -> bool:
    ...
```

## Key Insight

With at most 200 blocked cells, the maximum area they can enclose is `200 * 200 / 2 = 20000` cells (a triangle arrangement).

So if BFS from `source` finds more than `20000` cells without being blocked, it has escaped the enclosed region and can reach `target`.

Conversely, if `source` BFS stays within `20000` cells and `target` is not reached, `source` is enclosed.

Run BFS from both `source` and `target`. If both escape or one reaches the other, return `True`.

## Algorithm

Define `bfs(start, goal)`:
- BFS up to `limit = len(blocked)^2 // 2` cells.
- If we reach `goal` or visit more than `limit` cells, return `True`.
- Otherwise return `False`.

Return `bfs(source, target) and bfs(target, source)`.

## Correctness

If `source` can visit more than `limit` cells without hitting the goal, it has escaped any possible enclosed region formed by the blocked cells. Similarly for `target`. Both must be able to escape (or find each other) for a path to exist.

## Edge Cases

- Mark nodes or cells as visited at enqueue/discovery time to avoid duplicate work.
- Return the failure value when the destination is unreachable.
- Check grid or graph boundaries before reading neighbors.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(limit)` | BFS bounded by cell count limit |
| Space | `O(limit + B)` | Visited set and blocked set |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
from collections import deque

class Solution:
    def isEscapePossible(self, blocked: list[list[int]], source: list[int], target: list[int]) -> bool:
        if not blocked:
            return True

        blocked_set = set(map(tuple, blocked))
        limit = len(blocked) ** 2 // 2
        N = 10 ** 6

        def bfs(start, goal):
            sr, sc = start
            gr, gc = goal
            visited = {(sr, sc)}
            queue = deque([(sr, sc)])

            while queue:
                if len(visited) > limit:
                    return True
                r, c = queue.popleft()
                for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    nr, nc = r + dr, c + dc
                    if (0 <= nr < N and 0 <= nc < N
                            and (nr, nc) not in blocked_set
                            and (nr, nc) not in visited):
                        if nr == gr and nc == gc:
                            return True
                        visited.add((nr, nc))
                        queue.append((nr, nc))

            return False

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

## Testing

```python
def run_tests():
    s = Solution()

    assert s.isEscapePossible([], [0,0], [999999,999999]) == True
    assert s.isEscapePossible([[0,1],[1,0]], [0,0], [999999,999999]) == False
    assert s.isEscapePossible([[0,1],[1,0]], [0,0], [0,2]) == False

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| No blocks | `True` | Open grid |
| Corner blocked | `False` | Source `(0,0)` is enclosed |
| Corner blocked, close target | `False` | Source still enclosed |