864 · Shortest Path to Get All Keys

Walking a grid with keys and locks: you can revisit a cell if and only if you carry a different key inventory. The state space is $(r, c, \text{keyMask})$ with bitwise gating for locks.

Execution Stage

idle

INVARIANT Bitmask Re-visitation Invariant: Cells can and MUST be revisited when carrying a newly acquired key. The state space is $(r, c, \text{mask})$. Lock $L$ is passable if and only if (mask & (1 << (L - 'A'))) != 0.

Moves 0

Bitmask 0b00

Target Mask 0b11

Keys Collected:

Press Run to trace bitmask state-space BFS.

0 / 0

Speed

Java · Reference Algorithm

INTERVIEW SCRIPT

How to Present Shortest Path to Get All Keys to an Interviewer

1. The 3D State Space

"Because we can re-traverse empty corridors after picking up a key, the state cannot be just $(r, c)$. The state is the 3-tuple $(r, c, \text{keyMask})$."

2. Bitmask Representation

"There are at most 6 keys ($a$ to $f$). We encode collected keys as bits in an integer: key $ch$ sets bit $(1 \ll (ch - 'a'))$. The target mask with $K$ keys is $(1 \ll K) - 1$."

3. Lock Gating

"When encountering uppercase lock $L$, we check (mask & (1 << (L - 'A'))) != 0. If we hold the key, the door acts as an empty space; otherwise, it acts as a wall."

4. Complexity Bound

"The total number of states is $M \cdot N \cdot 2^K$. With $K \le 6$, $2^K \le 64$, giving at most $30 \times 30 \times 64 \approx 57,600$ states. Standard BFS runs in $O(MN \cdot 2^K)$ time."