Shortest Path to Get All Keys: BFS with Bitmask State

You are given an m x n grid where each cell is either empty (.), a wall (#), the start (@), a lowercase letter (a key), or an uppercase letter (a lock). You can move up, down, left, or right. You cannot walk through walls. You can only pass through a lock if you already hold the matching key (a opens A, b opens B, and so on). Return the minimum number of moves to collect every key in the grid. If it is impossible, return -1.

This is LeetCode 864: Shortest Path to Get All Keys, a hard problem that combines grid BFS with bitmask state compression. The trick is realizing that your BFS state is not just your position on the grid, but also which keys you are currently carrying.

Why this problem matters

Standard grid BFS tracks visited cells to avoid revisiting them. But in this problem, visiting the same cell with a different set of keys is a completely different situation. Cell (2,2) with key a in hand is not the same as cell (2,2) without any keys, because having key a lets you walk through lock A. If you use a simple visited set based on position alone, you will prune valid paths.

This problem teaches you to expand your notion of "state" in BFS. Instead of tracking just (row, col), you track (row, col, keys_bitmask). Each unique combination is a separate node in your implicit state graph. This same idea of augmented BFS state shows up in many hard graph problems, and once you internalize it, those problems become much more approachable.

The brute force approach

A naive approach would try all possible orderings of key collection and find the shortest path for each ordering. For each permutation of keys, you could run BFS between consecutive key locations and sum up the distances.

from itertools import permutations
from collections import deque

def shortest_path_brute(grid):
    m, n = len(grid), len(grid[0])
    keys = {}
    start = None
    for r in range(m):
        for c in range(n):
            if grid[r][c] == '@':
                start = (r, c)
            elif grid[r][c].islower():
                keys[grid[r][c]] = (r, c)

    def bfs(sr, sc, tr, tc, held):
        visited = set()
        visited.add((sr, sc))
        queue = deque([(sr, sc, 0)])
        while queue:
            r, c, d = queue.popleft()
            if r == tr and c == tc:
                return d
            for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited:
                    ch = grid[nr][nc]
                    if ch == '#':
                        continue
                    if ch.isupper() and ch.lower() not in held:
                        continue
                    visited.add((nr, nc))
                    queue.append((nr, nc, d + 1))
        return float('inf')

    best = float('inf')
    key_list = list(keys.keys())
    for perm in permutations(key_list):
        total = 0
        cr, cc = start
        held = set()
        for k in perm:
            tr, tc = keys[k]
            total += bfs(cr, cc, tr, tc, held)
            held.add(k)
            cr, cc = tr, tc
        best = min(best, total)
    return best if best < float('inf') else -1

This explores k! orderings (where k is the number of keys), and each ordering runs multiple BFS calls. For 6 keys that is 720 orderings, each with up to 6 BFS calls over the full grid. It works for tiny inputs but does not scale.

The key insight: BFS over (row, col, keys_bitmask) states

Instead of choosing an order to collect keys, let BFS discover the optimal order naturally. The state for BFS becomes a triple: (row, col, keys_bitmask). The bitmask is an integer where bit i is 1 if you hold the i-th key (mapping a to bit 0, b to bit 1, and so on).

The target state is any position where the mask equals (1 << k) - 1, meaning every key has been collected. BFS guarantees the first time you reach that mask is via the shortest path, because every move has cost 1.

Walking through it step by step

Let's trace BFS through the grid ["@.a.#", "###.#", "b.A.B"]. There are 2 keys (a and b), so the target mask is (1 << 2) - 1 = 3 (binary 11).

BFS processes states level by level. When we pick up key a at position (0,2), the bitmask changes from 00 to 01. This creates a new state that is distinct from visiting (0,2) without any keys. Eventually BFS finds a path to key b at (2,0) with both bits set (mask = 11), confirming all keys are collected. The distance at that point is the answer.

The optimal solution

from collections import deque

def shortest_path_all_keys(grid):
    m, n = len(grid), len(grid[0])
    total_keys = 0
    start_r = start_c = 0

    for r in range(m):
        for c in range(n):
            if grid[r][c] == '@':
                start_r, start_c = r, c
            elif grid[r][c].islower():
                total_keys += 1

    target = (1 << total_keys) - 1
    visited = set()
    visited.add((start_r, start_c, 0))
    queue = deque([(start_r, start_c, 0, 0)])

    while queue:
        r, c, keys, dist = queue.popleft()

        if keys == target:
            return dist

        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            if nr < 0 or nr >= m or nc < 0 or nc >= n:
                continue
            ch = grid[nr][nc]
            if ch == '#':
                continue
            if ch.isupper() and not (keys & (1 << (ord(ch) - ord('A')))):
                continue

            new_keys = keys
            if ch.islower():
                new_keys = keys | (1 << (ord(ch) - ord('a')))

            if (nr, nc, new_keys) not in visited:
                visited.add((nr, nc, new_keys))
                queue.append((nr, nc, new_keys, dist + 1))

    return -1

Complexity analysis

The key observation is that k is at most 6 per the problem constraints, so 2^k is at most 64. The total state space is m * n * 64, which for a 30x30 grid is 57,600 states. BFS handles this easily.

Building blocks

1. BFS for shortest path on a grid

The core BFS pattern for finding the shortest path in an unweighted grid is the foundation here. You process states level by level, using a queue and a visited set:

queue = deque([(start_r, start_c, 0)])
visited = {(start_r, start_c)}

while queue:
    r, c, dist = queue.popleft()
    for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
        nr, nc = r + dr, c + dc
        if valid(nr, nc) and (nr, nc) not in visited:
            visited.add((nr, nc))
            queue.append((nr, nc, dist + 1))

This template appears in Number of Islands, Rotting Oranges, and many other grid problems. The only difference here is that the state includes a bitmask alongside the position.

2. Bitmask state encoding for subset tracking

When you need to track which items from a small set have been collected, a bitmask integer is the most compact and efficient encoding:

keys = 0
keys = keys | (1 << key_index)
has_key = keys & (1 << key_index)
all_collected = keys == (1 << total_keys) - 1

This technique shows up in Shortest Path Visiting All Nodes, traveling salesman DP, and any problem where the state involves a subset of up to ~20 items. The bitmask makes the state hashable, comparable, and memory-efficient.

Edge cases

• No keys in the grid: If there are zero keys, the answer is 0. The target mask is (1 << 0) - 1 = 0, and the starting state already satisfies it.
• Start position is blocked: If the start is surrounded by walls on all sides, BFS finds no neighbors and the queue empties. Return -1.
• Lock without the matching key: BFS skips the lock cell until the state includes the required key bit. If no path reaches the key first, that lock stays impassable.
• Key behind a lock: You might need key a to unlock A to reach key b. BFS handles this naturally because it explores all reachable states at each distance level.
• Multiple paths to the same key: BFS may reach a key from different directions. The visited set ensures each (row, col, mask) is processed only once, so the first arrival is always the shortest.
• All keys adjacent to start: The answer is simply the number of keys, since you pick one up per step.

Common mistakes

1. Using (row, col) as the only visited key. This is the most common bug. If you ignore the bitmask in your visited set, you will skip valid states where you revisit a cell with different keys. The visited set must include the mask.

2. Forgetting to check locks. When moving to a cell with an uppercase letter, you must verify that the corresponding key bit is set. Skipping this check lets you walk through locked doors.

3. Not updating the mask when picking up a key. When you step onto a key cell, you must OR the key's bit into the mask before checking visited or enqueuing. If you forget, the mask never changes and BFS never reaches the target.

4. Off-by-one in key indexing. Key a maps to bit 0, key b to bit 1. Using ord(ch) - ord('a') gives the correct index. Using ord(ch) directly gives huge bit positions and breaks the bitmask.

From understanding to recall

You have seen how BFS with (row, col, keys_bitmask) state solves Shortest Path to Get All Keys. The bitmask update on key pickup, the lock check with bitwise AND, the target mask computation. It all makes sense when you read through it. But in an interview, you need to write the key-index mapping, the lock gate condition, and the augmented BFS loop from memory.

Spaced repetition makes those details automatic. CodeBricks drills the grid-BFS building block and the bitmask-state-encoding pattern independently. You type each piece from scratch at increasing intervals until the code flows out without hesitation. When a bitmask BFS problem appears in your interview, you do not pause to reconstruct how to combine position with key state. You just write it.

Related posts

• Number of Islands - The foundational grid BFS/DFS pattern that this problem builds on
• Open the Lock - BFS on an implicit state graph, where lock combinations are nodes and moves are edges
• Shortest Path Visiting All Nodes - Another BFS + bitmask problem where you track visited nodes as bits
• Word Ladder - BFS shortest path on an implicit graph, showing the same BFS template in a different context
• Keys and Rooms - A simpler key-and-lock graph traversal that introduces the idea of conditional access

The grid BFS plus bitmask state pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.