LeetCode 864: Shortest Path to Get All Keys

Problem Restatement

We are given a 2D grid.

Each cell contains one character:

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

Function shape:

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

Examples

Example 1:

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

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

The answer is:

8

Example 2:

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

We can reach both keys while respecting the locks.

The answer is:

6

Example 3:

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:

-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:

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

keys == (1 << k) - 1

So BFS state becomes:

(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:

target_keys = (1 << key_count) - 1

Run BFS from:

(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:

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

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

Implementation

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:

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:

target_keys = (1 << key_count) - 1

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

0b111

The BFS queue stores:

(row, col, keys, moves)

The visited set stores:

(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:

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

we turn on the corresponding bit.

For an uppercase lock:

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:

if keys == target_keys:
    return moves

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

Testing

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: