> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Shortest Path to Get All Keys Python Solution

> Tested Python solution for LeetCode 864 with 22 pytest cases. Generate a practice environment with lcpy.

LeetCode 864, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Bit Manipulation](/catalog/topics/bit-manipulation), [Breadth-First Search](/catalog/topics/breadth-first-search), [Matrix](/catalog/topics/matrix). [View on LeetCode](https://leetcode.com/problems/shortest-path-to-get-all-keys/description/).

Generate this problem as a practice environment: tested reference solution, 22 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 864   # by problem number
lcpy gen -s shortest_path_to_get_all_keys   # by problem name
```

## Problem

You are given an `m x n` grid `grid` where:

* `'.'` is an empty cell.
* `'#'` is a wall.
* `'@'` is the starting point.
* Lowercase letters represent keys.
* Uppercase letters represent locks.

You start at the starting point and one move consists of walking one space in one of the four cardinal directions. You cannot walk outside the grid, or walk into a wall.

If you walk over a key, you can pick it up and you cannot walk over a lock unless you have its corresponding key.
For some `1 <= k <= 6`, there is exactly one lowercase and one uppercase letter of the first `k` letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.

Return the lowest number of moves to acquire all keys. If it is impossible, return `-1`.

### Examples

```
Input: grid = ["@.a..","###.#","b.A.B"]
Output: 8
Explanation: Note that the goal is to obtain all the keys not to open all the locks.
```

```
Input: grid = ["@..aA","..B#.","....b"]
Output: 6
```

```
Input: grid = ["@Aa"]
Output: -1
```

### Constraints

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 30`
* `grid[i][j]` is a letter, `'.'`, `'#'`, or `'@'`.
* There is exactly one `'@'` in the grid.
* The number of keys in the grid is in the range `[1, 6]`.
* Each key in the grid is unique.
* Each key in the grid has a matching lock.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/shortest_path_to_get_all_keys/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/shortest_path_to_get_all_keys/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import deque


class Solution:
    # Time: O(m * n * 2^k)
    # Space: O(m * n * 2^k)
    def shortest_path_all_keys(self, grid: list[str]) -> int:
        m, n = len(grid), len(grid[0])
        keys = 0
        start_r = start_c = 0
        for r in range(m):
            for c in range(n):
                ch = grid[r][c]
                if ch == "@":
                    start_r, start_c = r, c
                elif ch.islower():
                    keys |= 1 << (ord(ch) - ord("a"))

        queue: deque[tuple[int, int, int]] = deque([(start_r, start_c, 0)])
        seen = {(start_r, start_c, 0)}
        moves = 0
        while queue:
            for _ in range(len(queue)):
                r, c, held = queue.popleft()
                if held == keys:
                    return moves
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr, nc = r + dr, c + dc
                    if not (0 <= nr < m and 0 <= nc < n):
                        continue
                    ch = grid[nr][nc]
                    if ch == "#":
                        continue
                    if ch.isupper() and not held & (1 << (ord(ch.lower()) - ord("a"))):
                        continue
                    nxt = held | (1 << (ord(ch) - ord("a"))) if ch.islower() else held
                    state = (nr, nc, nxt)
                    if state not in seen:
                        seen.add(state)
                        queue.append(state)
            moves += 1
        return -1
```

## Complexity

| Time | Space |
| - | - |
| O(m \* n \* 2^k) | O(m \* n \* 2^k) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.