Daily bit(e) of C++ | Shortest path to all keys
Daily bit(e) of C++ #210, Common interview problem: Shortest path to all keys.
Today we will look at a common C++ interview problem: Shortest path to all keys.
Given a map represented as std::vector<std::vector<char>>, where:
# are impassable walls
@ is the entrance to the puzzle
the first k lowercase letters are keys
the corresponding uppercase letters are locked doors
Assuming k <= 6, determine the length of the shortest path that collects all keys, -1 if none exists.
For example, on the above map, we first have to collect the red key (2 steps), then the green key (3 steps) and finally the blue key (10 steps).
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://godbolt.org/z/9dW6Gzrer.
Solution
Determining the shortest path is the domain of breadth-first search. However, the keys introduce a complication.
We could try to deal with the keys; however, we have a very conservative bound on the number of keys (six).
We can therefore apply the multi-dimensional trick for the bread-first search. When we step on a key, we can move to a maze floor that never contained the corresponding door. There are 2^k unique floors, which for our upper bound leads to a maximum of 64 floors.
With this three-dimensional maze, we can apply the standard breadth-first search, leading to an O(m*n*2^k) time and space complexity.
