Keys and Doors — Solution & Editorial

Back to the Problem

BFS over the EXPANDED state (position, key-bitmask) — up to N·M·2⁶ states. Plain positional BFS cannot represent 'may I pass this door'.

Complexity: O(N M 2^K)