864. Shortest Path to Get All Keys

Problem¶

Given a grid containing walls, keys, locks, and a starting cell, return the minimum number of cardinal moves needed to collect every key. A lock is passable only after collecting its lowercase key; return -1 if collection is impossible.

grid = ["@.a..", "###.#", "b.A.B"] -> 8 moves

Key trick¶

Run BFS over states (row, column, key_mask), not just cells; the same cell may need revisiting after obtaining different keys.

Trap¶

Marking only cells as visited can discard valid paths with new keys.
Mark states visited when enqueuing them, or duplicates can grow rapidly.
The goal is collecting every key, not opening every lock.

Why is it interesting?¶

Adding the key bitmask turns a pathfinding problem with changing permissions into a standard shortest-path search on an expanded graph.

Python solution¶

from collections import deque


class Solution:
    def shortestPathAllKeys(self, grid: list[str]) -> int:
        m, n = len(grid), len(grid[0])
        target = 0
        start = (-1, -1)

        for r in range(m):
            for c in range(n):
                ch = grid[r][c]
                if ch == "@":
                    start = (r, c)
                elif ch.islower():
                    target |= 1 << (ord(ch) - ord("a"))

        # State includes the keys held because they determine which moves
        # are legal and whether revisiting a cell is useful.
        q = deque([(start[0], start[1], 0, 0)])
        seen = {(start[0], start[1], 0)}

        while q:
            r, c, mask, dist = q.popleft()

            if mask == target:
                return dist

            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():
                    key_bit = 1 << (ord(ch.lower()) - ord("a"))
                    if not mask & key_bit:
                        continue

                if ch.islower():
                    mask |= 1 << (ord(ch) - ord("a"))

                state = (nr, nc, mask)
                if state not in seen:
                    seen.add(state)
                    q.append((*state, dist + 1))

        return -1

Time: \(O(mn2^k)\), where \(k\) is the number of keys.
Space: \(O(mn2^k)\).

Comment on my solution¶

Finding @ and all keys before searching is correct.
BFS is the right choice because every move has equal cost.
Start BFS from @; searching backward from keys does not model locks or multiple targets well.
Backtracking is unnecessary and may explore exponentially many paths without BFS’s shortest-path guarantee.
Cells may be revisited, but each state (row, column, key_mask) should be visited only once.
Plain connectivity is insufficient because obtaining keys changes which cells are reachable.
Topological sorting does not work reliably: dependencies depend on chosen paths, and alternative routes may bypass locks.
Stop when BFS first reaches a state whose mask contains every key; return -1 if the queue becomes empty.

# Ideas:
# - we need to find @ cell
# - we need to count keys before search the shortest way to find them
# - as we search the minimum moves, BFS may be appropriate
# - should we start BFS from target or the keys?
# - maybe some backtracking??
# - when searching the matrix for keys we should allow revisiting cells
#   - so we can't just have a visited sets to discard cells
#   - so when do we stop searching
# - Can all keys can be reached?
#   - compute the key needed because of locks encountered to reach a key
#   - Does the keys and the starting point form a connected component?
#   - Maybe a topological sort would work.
#     - to reach that key you first have to get these other keys because
#       of the locks you'll encounter

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