# LeetCode 1091: Shortest Path in Binary Matrix

## Problem Restatement

We are given an `n x n` binary matrix `grid`.

A clear path goes from `(0, 0)` to `(n-1, n-1)` using only cells with value `0`, moving in 8 directions.

Return the length of the shortest clear path, or `-1` if no such path exists.

The path length counts the number of cells visited.

The official constraints state that `n == grid.length == grid[i].length`, `1 <= n <= 100`, and `grid[i][j]` is `0` or `1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Binary grid |
| Output | Length of shortest clear path, or `-1` |
| Clear path | Only cells with value `0`, 8-directional movement |

Function shape:

```python
def shortestPathBinaryMatrix(grid: list[list[int]]) -> int:
    ...
```

## Examples

Example 1:

```python
grid = [[0,1],[1,0]]
```

Path: `(0,0)` → `(1,1)`. Length 2.

Answer:

```python
2
```

Example 2:

```python
grid = [[0,0,0],[1,1,0],[1,1,0]]
```

One shortest path is `(0,0) -> (0,1) -> (1,2) -> (2,2)`.

The length is `4` because the problem counts visited cells, including the start and the end.

Answer:

```python
4
```

## Key Insight

BFS guarantees the shortest path. Start from `(0,0)` and expand in all 8 directions. Return the distance when `(n-1, n-1)` is reached.

## Algorithm

1. If `grid[0][0] == 1` or `grid[n-1][n-1] == 1`, return `-1`.
2. BFS from `(0, 0)` with distance `1`.
3. Expand to all 8 neighbors that are `0` and unvisited.
4. Return distance when `(n-1, n-1)` is reached, or `-1` if BFS exhausts.

## 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(n^2)` | Each cell visited at most once |
| Space | `O(n^2)` | Queue and visited marking |

## 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 shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int:
        n = len(grid)
        if grid[0][0] == 1 or grid[n-1][n-1] == 1:
            return -1

        queue = deque([(0, 0, 1)])
        grid[0][0] = 1

        for r, c, dist in queue:
            if r == n - 1 and c == n - 1:
                return dist
            for dr in [-1, 0, 1]:
                for dc in [-1, 0, 1]:
                    if dr == 0 and dc == 0:
                        continue
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                        grid[nr][nc] = 1
                        queue.append((nr, nc, dist + 1))

        return -1
```

## Testing

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

    assert s.shortestPathBinaryMatrix([[0,1],[1,0]]) == 2
    assert s.shortestPathBinaryMatrix([[0,0,0],[1,1,0],[1,1,0]]) == 4
    assert s.shortestPathBinaryMatrix([[1,0,0],[1,1,0],[1,1,0]]) == -1

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| 2x2 diagonal | `2` | Direct diagonal path |
| 3x3 grid | `4` | Shortest path through clear cells |
| Blocked start | `-1` | Start cell is blocked |