Keys and Rooms

Средняя№841граф

Есть n запертых комнат с номерами от 0, открыта только комната 0. В каждой комнате лежат ключи, каждый открывает одну комнату. Нужно понять, получится ли попасть во все комнаты. Наш пример: в комнатах от 0 до 4 лежат ключи [1, 3], [3, 0], [4], [], [2] — ответ false.

841 Keys and RoomsРазбор · 1×

Пример: понять, откроются ли все комнаты, если в них лежат ключи [1, 3], [3, 0], [4], [], [2].

0ключи1, 31ключи3, 02ключи43ключи—4ключи2очередьначало слева—
заперта, ключа пока нетключ найден, в очередикомнату обыскиваемобысканатак и не открыли

Комната 0 открыта с самого начала: visited = {0}

01/22
сначала · назад · пуск · шаг
Скорость
1function canVisitAllRooms(rooms):
2 visited = {0}
3 queue = [0]
4 while queue is not empty:
5 room = queue.popFront()
6 for key in rooms[room]:
7 if key not in visited:
8 visited.add(key)
9 queue.pushBack(key)
10 return visited.size == rooms.size
состояние
visited
{0}
queue
–
room
–
key
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Ключ — это ребро из комнаты, где он лежит, в комнату, которую он открывает, поэтому попасть можно ровно в те комнаты, до которых есть путь из комнаты 0.
  2. Комнату отмечаем, как только нашли ключ от неё, поэтому каждая комната попадает в очередь и обыскивается один раз, сколько бы ключей от неё ни было.
  3. Когда очередь опустела, все ключи во всех открытых комнатах уже испробованы; неотмеченная комната — та, ключа от которой не достать.

Сложность

Время O(n + k), где k — число ключей: каждую комнату обыскиваем один раз и на каждый ключ смотрим один раз. Память O(n) на visited и очередь.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.