2

Помогите решить задачу. Скорее всего неверный алгоритм. Я решаю ее на stepik и там не показывает какой тест не проходит, отчего не пойму где ошибка. И решение не засчитывает. Я попробовал решить без переменной v, т.к. не понятно как ее использовать.

Задача:

Представьте, что вы попали в большой замок, в котором N комнат (под номерами 0..N-1), а вы находитесь в комнате под номером 0. В каждой комнате спрятаны ключи, которые позволяют попасть в другую комнату.

В каждой комнате i есть список чисел rooms[i], обозначающий список ключей, который хранится в этой комнате. Каждый ключ j открывает некоторую комнату под номером v: rooms[i][j] = v

В начале все комнаты закрыты. Верните True, если все комнаты в замке могут быть открыты, а иначе верните False.

Вот мой код:

class Solution:        
def canVisitAllRooms(self, rooms: list):
    verifyList=[]
    tst = [i for i in range(len(rooms))]
    for i in range(len(rooms)):
        tf=0
        if len(rooms[i])>0:
            for j in rooms[i]:
                if i != j and j in range(len(rooms)): tf += 1
                print('ключ из комнаты', i, 'открывает комнату', j)
            print('совпадений - ', tf)
            verifyList.append(tf)

    if 0 in verifyList: return False
    else: return True
2
  • 1
    Решил задачу :) 8 мая 2020 в 15:35
  • 1
    Опубликуйте свое решение как ответ.
    – S. Nick
    8 мая 2020 в 15:45

2 ответа 2

3

Решил в итоге задачу, за неимением ответов на вопрос) получилось вот так:

def canVisitAllRooms(self, rooms: list):
    # создаем закрытые комнаты
    visited = [False] * (len(rooms))

    def dfs(s, visited):
        #если комната открыта, то true
        if visited[s]:
            return True
        # иначе открываем текущую комнату
        visited[s] = True
        # и проверяем ключи из этой комнаты
        for neighbor in rooms[s]:
            #print(neighbor)
            dfs(neighbor, visited)


    s=0
    #print(dfs(0, visited))
    dfs(0, visited)

    # проверка открытых комнат
    if False in visited: return False
    else: return True
1

Предлагаю итеративное решение.

Оно имеет следующие преимущества:

  • Максимальная, дефолтная глубина рекурсии в Python 1000 вызовов, соответственно рекурсивное решение не сможет обработать больше 1000 комнат.
  • Для хранения посещённых комнат используется структура данных set, что позволяет проверять посещена ли комната за константное время - O(1).

Алгоритм:

  1. Создаём набор (set) ключей, помещаем в него ключ от комнаты № 0.
  2. Достаём ключ из набора, если он от непосещённой комнаты, заходим в неё.
  3. Добавляем все ключи из новой комнаты в набор ключей.
  4. Добавляем комнату в посещённые.
  5. Если в наборе остались ключи, возращаемся в пункт 2.
  6. Возращаем результат сравнения количества посещённых комнат с общим количеством.
class Solution:
    def canVisitAllRooms(self, rooms):
        key_set = {0} 
        visited = set()

        while key_set:
            key = key_set.pop()

            if key not in visited:
                key_set.update(rooms[key])
                visited.add(key)

        return len(visited) == len(rooms)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.