BFS with Augmented State — Multi-Dimensional Search

Grid + keys problem

// State: (row, col, keyBitmask)
record State(int r, int c, int mask) {}
Map dist = new HashMap<>();
// If we pick up key at (r,c), new mask has bit set

Complexity

O(V × K) where K = number of extra state dimensions. Grid with K keys: O(R × C × 2^K).

Applications

Puzzle games (keys, orbs). Robot with limited fuel. Portal problems. Multi-agent coordination.

Meet-in-the-middle

Two agents: joint state = O(V²). Search each half of moves separately, meet at intersection.