Prepared by: Vito Anić

Let us first solve a simpler problem. We have a similar labyrinth, but there are no colors. Some doors are locked, and some are unlocked. Teo and Gabriel can pass through an unlocked door, but they cannot pass through a locked door. How to determine if is it possible to reach the rest of the team? This can be solved with DFS that spreads from the starting point. If it reaches the required goal, then it is possible to go from the start to the end, and if it does not, then it is not possible.

Now we can solve the whole problem. There are only four door colors, and it is possible to go through every combination of colors and try to reach the end by using only the chosen colors. To clarify, all the doors with the colors we chose will be 'unlocked', and the rest will be locked. Now we have the simpler problem from the previous paragraph. For all the combinations of colors for which we can reach the end, we take the one that uses the least colors. Total time complexity is ~\mathcal O(nmq \cdot 2^4)~.