Daily bit(e) of C++ | Locked rooms
Daily bit(e) of C++ #163, Common interview problem: Locked rooms
Today we will look at a common C++ interview problem: Locked rooms.
Given an array of n locked rooms, each room containing 0..n distinct keys, determine whether you can visit each room. You are given the key to room zero, and each room can only be opened with the corresponding key (however, there may be 0..n copies of that key).
Assume that you can freely move between rooms (i.e. the only thing you need is the key).
For example, in the above situation, we can open the red lock to collect the blue and green keys, then the green lock to collect the brown key, and finally, the remaining blue and brown locks.
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://compiler-explorer.com/z/zx85hGx7T.
Solution
This is a reachability problem, pointing us to the depth-first search. More specifically, we are trying to determine whether we can reach all the keys (reaching all keys allows us to open all doors).
