Почему это работает
- Ключ — это ребро из комнаты, где он лежит, в комнату, которую он открывает, поэтому попасть можно ровно в те комнаты, до которых есть путь из комнаты 0.
- Комнату отмечаем, как только нашли ключ от неё, поэтому каждая комната попадает в очередь и обыскивается один раз, сколько бы ключей от неё ни было.
- Когда очередь опустела, все ключи во всех открытых комнатах уже испробованы; неотмеченная комната — та, ключа от которой не достать.
Сложность
Время O(n + k), где k — число ключей: каждую комнату обыскиваем один раз и на каждый ключ смотрим один раз. Память O(n) на visited и очередь.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗