Fewest Moves to Collect Every Key in a Grid With Locked Cells
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a rectangular grid as a list of equal-length strings. Each character is one of:
- `'@'`: the starting cell (there is exactly one); apart from that it is an empty cell
- `'.'`: an empty cell
- `'#'`: a wall
- a lowercase letter from `'a'` to `'f'`: a key
- an uppercase letter from `'A'` to `'F'`: a lock, opened by the key with the same letter in lowercase
In one move you step from your current cell to one of its four orthogonal neighbors. You may not leave the grid or enter a wall, and you may enter a lock cell only if you already hold the matching key. Entering a key cell picks that key up. Return the minimum number of moves needed to hold every key in the grid, or `-1` if it cannot be done.
### Function Signature
```python
def min_moves_all_keys(grid: List[str]) -> int:
```
### Rules
- Keys are never used up: once you hold a key, its lock can be crossed any number of times.
- Any cell, including the start, may be visited more than once.
- Counting stops as soon as the last key is picked up; you do not need to return anywhere.
- Each step costs one move; picking up a key costs nothing extra.
### Constraints
- `1 <= len(grid) <= 30` and `1 <= len(grid[r]) <= 30`, with all rows the same length
- Every character is `'@'`, `'.'`, `'#'`, a letter from `'a'` to `'f'`, or a letter from `'A'` to `'F'`
- Exactly one `'@'`
- If the grid holds `k` keys, then `1 <= k <= 6`, and the keys are exactly the first `k` lowercase letters, each appearing once
- Each lock letter appears at most once and matches one of the `k` keys
### Examples
**Example 1**
```
grid = ["@.a",
".#A",
"..b"]
output = 4
```
Two moves along the top row reach key `a`; holding it, you can step down through lock `A` and reach key `b` two moves later.
**Example 2**
```
grid = ["@.A",
".#b",
"a..",]
output = 5
```
Lock `A` blocks the short route along the top row before key `a` is held. Going down the left column picks up key `a` after two moves, and three more moves along the bottom row and up reach key `b`.
**Example 3**
```
grid = ["@.a",
"#B#",
"b.A"]
output = -1
```
Key `b` can only be reached through lock `B`, which itself needs key `b`.
Overview: A grid path problem in which you start at one cell, must pick up every key, and may only enter a locked cell after collecting its matching key, returning the fewest moves or -1. It tests modeling search progress that depends on items collected along the way and detecting layouts that cannot be solved.
Read the full Microsoft Software Engineer interview experience this question came from