Shortest Path to Get All Keys — Hard Problem & Solution

Problem statement

You are given an m x n grid as a list of strings, one per row:

• '.' is an empty cell and '#' is a wall,
• '@' is the starting point (there is exactly one),
• lowercase letters 'a'–'f' are keys and uppercase letters 'A'–'F' are locks.

Each move goes one cell up, down, left or right. You cannot leave the grid or enter a wall. Walking onto a key picks it up; you may enter a lock only if you already hold its matching key.

The grid holds k keys (1 <= k <= 6), and they are exactly the first k letters of the alphabet, each with exactly one matching lock. Return the fewest moves needed to collect all keys, or -1 if that is impossible.

Example 1

Input: grid = ["@.#b","a.A.","#..B"]
Output: 5
Explanation: Take `a` (1 move), then go (1,1) → (1,2) through lock `A` → (1,3) → (0,3) for `b`.

Example 2

Input: grid = ["@#a"]
Output: -1
Explanation: The wall cuts the start off from the only key.

Example 3

Input: grid = ["Aa@bB"]
Output: 3

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 30
• grid[i][j] is an English letter, '.', '#' or '@'
• there is exactly one '@' in the grid
• the number of keys is in the range [1, 6]
• each key is unique and has a matching lock
• the keys and locks are the first k letters of the alphabet

How to solve Shortest Path to Get All Keys

Breadth-first search over the augmented state (cell, key mask); every move costs 1, so the first time the mask is full is the shortest route.

Approach

1. Find the start and the number of keys k; the goal mask is 2^k − 1.
2. BFS from (start, 0), marking states visited in an m × n × 2^k table.
3. From a state, try the four neighbours: skip walls, skip a lock whose key bit is clear, and OR in the bit of a key.
4. Return distance + 1 as soon as a new state has the full mask; return -1 if the BFS ends.

Why it works

Carrying the key set in the state makes the move rules depend only on the state, so the problem is an unweighted shortest path in a finite graph of at most m · n · 64 states, which BFS solves exactly. Revisiting a cell with a different key set is allowed and necessary — that is how routes that fetch a key and come back are found.

Complexity

• Time — O(m · n · 2^k)
• Space — O(m · n · 2^k)

Pitfalls

• Marking a cell visited regardless of the key mask blocks the back-tracking routes the puzzle needs.
• A lock without its key is a wall for now, not forever.
• The goal is all keys, not any particular cell — check the mask, not the position.

Reference solution

Python

from typing import List
from collections import deque

def shortestPathAllKeys(grid: List[str]) -> int:
    m, n = len(grid), len(grid[0])
    keys = 0
    sr = sc = 0
    for r in range(m):
        for c in range(n):
            ch = grid[r][c]
            if ch == '@':
                sr, sc = r, c
            elif 'a' <= ch <= 'f':
                keys = max(keys, ord(ch) - 96)
    full = (1 << keys) - 1
    seen = [[[False] * (1 << keys) for _ in range(n)] for _ in range(m)]
    seen[sr][sc][0] = True
    q = deque([(sr, sc, 0, 0)])
    while q:
        r, c, mask, d = q.popleft()
        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 'A' <= ch <= 'F' and not (mask >> (ord(ch) - 65)) & 1:
                continue
            nm = mask
            if 'a' <= ch <= 'f':
                nm |= 1 << (ord(ch) - 97)
            if seen[nr][nc][nm]:
                continue
            if nm == full:
                return d + 1
            seen[nr][nc][nm] = True
            q.append((nr, nc, nm, d + 1))
    return -1

JavaScript

var shortestPathAllKeys = function(grid) {
    var m = grid.length, n = grid[0].length, keys = 0, start = 0;
    for (var r = 0; r < m; r++) {
        for (var c = 0; c < n; c++) {
            var ch = grid[r].charCodeAt(c);
            if (ch === 64) start = r * n + c;
            else if (ch >= 97 && ch <= 102 && ch - 96 > keys) keys = ch - 96;
        }
    }
    var full = (1 << keys) - 1;
    var seen = [];
    for (var i = 0; i < m * n * 64; i++) seen.push(false);
    var qc = [start], qm = [0], qd = [0];
    seen[start * 64] = true;
    var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    for (var h = 0; h < qc.length; h++) {
        var cr = Math.floor(qc[h] / n), cc = qc[h] % n, mask = qm[h], d = qd[h];
        for (var k = 0; k < 4; k++) {
            var nr = cr + dr[k], nc = cc + dc[k];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            var x = grid[nr].charCodeAt(nc);
            if (x === 35) continue;
            if (x >= 65 && x <= 70 && ((mask >> (x - 65)) & 1) === 0) continue;
            var nm = mask;
            if (x >= 97 && x <= 102) nm |= 1 << (x - 97);
            var id = (nr * n + nc) * 64 + nm;
            if (seen[id]) continue;
            if (nm === full) return d + 1;
            seen[id] = true;
            qc.push(nr * n + nc); qm.push(nm); qd.push(d + 1);
        }
    }
    return -1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Remove Boxes Hard
• Number of Squareful Arrays Hard
• Closest Subsequence Sum Hard
• Maximum Number of Achievable Transfer Requests Hard
• 24 Game Hard
• Verbal Arithmetic Puzzle Hard