# LeetCode 864: Shortest Path to Get All Keys

## Problem Restatement

We are given a 2D grid.

Each cell contains one character:

| Character | Meaning |
|---|---|
| `"."` | Empty cell |
| `"#"` | Wall |
| `"@"` | Starting position |
| `"a"` to `"f"` | Key |
| `"A"` to `"F"` | Lock |

We start at `"@"`.

One move means walking one cell up, down, left, or right.

We cannot walk outside the grid.

We cannot walk through walls.

When we step on a key, we pick it up.

We cannot pass through a lock unless we already have the matching lowercase key.

Return the minimum number of moves needed to collect all keys.

If it is impossible, return `-1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `grid`, a list of strings |
| Output | Minimum number of moves to collect all keys |
| Failure case | Return `-1` if not possible |
| Keys | At most 6 keys, from `"a"` to `"f"` |

Function shape:

```python
class Solution:
    def shortestPathAllKeys(self, grid: list[str]) -> int:
        ...
```

## Examples

Example 1:

```python
grid = ["@.a..", "###.#", "b.A.B"]
```

A shortest path collects key `"a"` first, then key `"b"`.

The answer is:

```python
8
```

Example 2:

```python
grid = ["@..aA", "..B#.", "....b"]
```

We can reach both keys while respecting the locks.

The answer is:

```python
6
```

Example 3:

```python
grid = ["@Aa"]
```

The lock `"A"` blocks the only path to key `"a"`.

We do not have key `"a"` yet, so we cannot pass through `"A"`.

The answer is:

```python
-1
```

## First Thought: BFS on the Grid

This is a shortest path problem.

Each move costs `1`.

That usually means BFS.

But ordinary BFS with only position `(row, col)` is not enough.

The same cell can have different meaning depending on which keys we have collected.

For example, reaching a cell without key `"a"` is different from reaching the same cell with key `"a"`, because the second state may now pass through lock `"A"`.

So the BFS state must include both:

1. Current position
2. Set of collected keys

## Key Insight

There are at most 6 keys.

That means we can store the collected keys as a bitmask.

Use bit `0` for key `"a"`, bit `1` for key `"b"`, and so on.

For example:

| Keys collected | Bitmask |
|---|---|
| none | `000000` |
| `"a"` | `000001` |
| `"b"` | `000010` |
| `"a", "b"` | `000011` |
| `"a", "c"` | `000101` |

If there are `k` keys, then all keys have been collected when:

```python
keys == (1 << k) - 1
```

So BFS state becomes:

```python
(row, col, keys)
```

where `keys` is the bitmask of collected keys.

## Algorithm

First scan the grid.

Find:

1. The starting position
2. The number of keys

Then compute:

```python
target_keys = (1 << key_count) - 1
```

Run BFS from:

```python
(start_row, start_col, 0)
```

For each state:

1. Try the four neighboring cells.
2. Skip the neighbor if it is outside the grid.
3. Skip the neighbor if it is a wall.
4. If it is a lock, check whether we have the matching key.
5. If it is a key, add it to the bitmask.
6. If the new bitmask equals `target_keys`, return the number of moves.
7. Otherwise, add the new state to the queue if it has not been visited.

## Correctness

The grid can be viewed as an unweighted graph of states.

A state is not just a cell. It is a triple `(row, col, keys)`, because the set of keys determines which future moves are legal.

There is an edge from one state to another if one valid move changes the position and possibly adds a key.

Every edge has cost `1`, because every move takes one step.

BFS explores states in increasing number of moves from the start. Therefore, the first time BFS reaches a state whose key bitmask contains all keys, that number of moves is the minimum possible.

The visited set stores full states, not only positions. This is necessary because visiting the same cell with more keys can allow new paths.

Thus, the algorithm returns the shortest path length that collects all keys, or `-1` if no such state is reachable.

## Complexity

Let:

```python
m = number of rows
n = number of columns
k = number of keys
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(m * n * 2^k)` | Each cell can be visited with each key mask |
| Space | `O(m * n * 2^k)` | The queue and visited set store states |

Since `k <= 6`, the bitmask factor is small.

## Implementation

```python
from collections import deque

class Solution:
    def shortestPathAllKeys(self, grid: list[str]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        start_row = 0
        start_col = 0
        key_count = 0

        for r in range(rows):
            for c in range(cols):
                cell = grid[r][c]

                if cell == "@":
                    start_row = r
                    start_col = c
                elif "a" <= cell <= "f":
                    key_count += 1

        target_keys = (1 << key_count) - 1

        queue = deque([(start_row, start_col, 0, 0)])
        visited = {(start_row, start_col, 0)}

        directions = [
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1),
        ]

        while queue:
            row, col, keys, moves = queue.popleft()

            if keys == target_keys:
                return moves

            for dr, dc in directions:
                next_row = row + dr
                next_col = col + dc

                if next_row < 0 or next_row >= rows:
                    continue

                if next_col < 0 or next_col >= cols:
                    continue

                cell = grid[next_row][next_col]

                if cell == "#":
                    continue

                next_keys = keys

                if "a" <= cell <= "f":
                    bit = ord(cell) - ord("a")
                    next_keys |= 1 << bit

                if "A" <= cell <= "F":
                    bit = ord(cell) - ord("A")

                    if not (keys & (1 << bit)):
                        continue

                state = (next_row, next_col, next_keys)

                if state in visited:
                    continue

                visited.add(state)
                queue.append((next_row, next_col, next_keys, moves + 1))

        return -1
```

## Code Explanation

We first scan the grid:

```python
for r in range(rows):
    for c in range(cols):
        cell = grid[r][c]
```

When we find `"@"`, we save the start position.

When we find a lowercase letter, we count one key.

The target bitmask is:

```python
target_keys = (1 << key_count) - 1
```

For example, if there are 3 keys, this is:

```python
0b111
```

The BFS queue stores:

```python
(row, col, keys, moves)
```

The visited set stores:

```python
(row, col, keys)
```

We do not include `moves` in `visited`, because if we have already reached the same position with the same keys, reaching it later is never better.

For a lowercase key:

```python
if "a" <= cell <= "f":
    bit = ord(cell) - ord("a")
    next_keys |= 1 << bit
```

we turn on the corresponding bit.

For an uppercase lock:

```python
if "A" <= cell <= "F":
    bit = ord(cell) - ord("A")

    if not (keys & (1 << bit)):
        continue
```

we check whether the matching key bit is already set.

If not, that move is illegal.

When BFS finds all keys:

```python
if keys == target_keys:
    return moves
```

we return immediately, because BFS guarantees this is the smallest number of moves.

## Testing

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

    assert s.shortestPathAllKeys(["@.a..", "###.#", "b.A.B"]) == 8

    assert s.shortestPathAllKeys(["@..aA", "..B#.", "....b"]) == 6

    assert s.shortestPathAllKeys(["@Aa"]) == -1

    assert s.shortestPathAllKeys(["@a"]) == 1

    assert s.shortestPathAllKeys(["@...a", ".###A", "b.BCc"]) == 10

    print("all tests passed")

test_shortest_path_all_keys()
```

Test meaning:

| Test | Why |
|---|---|
| `["@.a..", "###.#", "b.A.B"]` | Standard case with two keys and locks |
| `["@..aA", "..B#.", "....b"]` | Requires collecting keys before useful lock traversal |
| `["@Aa"]` | Lock blocks the only path |
| `["@a"]` | One key next to start |
| Larger mixed grid | Checks multiple keys, walls, and locks |