Задачи
November 26, 2021

Задача. Ключи к дверям

Задача: Даны N комнат, все комнаты заперты, кроме первой. Нельзя войти в запертую комнату без ключа.

Однако когда вы заходите в комнату, вы можете найти в ней набор разных ключей. На каждом ключе есть номер, обозначающий, какую комнату он открывает. Можно использовать эти ключи, чтобы разблокировать следующие комнаты.

Необходимо проверить можно ли посетить все комнаты.

Входные данные: rooms[] - масств, где rooms[i] - набор ключей, которые вы можете получить, посетив комнату i. Нумерация комнат и ключей начинается с 0.

Вывод: true - если вы можете посетить все комнаты, false в противном случае.

Примеры:

  1. rooms = [[1],[2],[3],[]]
    Output: true
    Пояснение: 1я (room[0]) комната открыта, в ней лежит ключ от 2й комнаты(room[1] = 1), далее забираем ключ от 3й и 4й комнаты.
  2. rooms = [[1,3],[3,0,1],[2],[0]]
    Output: false
    Пояснение: ключ от 3й комнаты (room[2] = 2) лежит в самой комнате, таким образом, пройти все комнаты не получится.

Разбор

Для решения этой задачи воспользуемся методом поиска в глубину. То есть из каждой посещенной комнаты запустим поиск по ключам, которые мы получили. Не забываем считать посещенные комнаты. Зная общее кол-во комнат, в конце мы просто проверим все ли мы смогли посетить.

Детали реализации смотрите в коде.

Реализация

Запустить код тут

https://dotnetfiddle.net/kCFrjZ