|
На космической станции, состоящей из отсеков (круглых комнат) и соединяющих их коридоров, произошел сбой электроснабжения, в результате чего связь с роботом, работающим на станции, прервалась. После восстановления работы станции выяснилось, что движение по коридорам, половина из которых оказались неосвещенными, возможно только по направлениям, указанным на схеме и занимает 1 минуту для каждого коридора. При этом неизвестно, в каком отсеке находится робот. Робот управляется командами из нулей и единиц, при этом 0 соответствует движению по освещенному коридору, а 1 – по неосвещенному. Передайте команду роботу, которая приведет его из любой комнаты в лабораторию (где находится выход). С момента начала движения робота его энергоснабжения хватит не более, чем на 5 минут. |
Одним из возможных способов решения поставленной задачи будет нахождение путей длины 5, ведущих ИЗ заданной вершины (лаборатории, вершины №3), то есть куда и по каким коридорам за 5 шагов можно попасть из этой вершины, двигаясь ПРОТИВ стрелок. Сначала из нее можно попасть в вершины №8 и №2 и двигаться можно только по неосвещенным коридорам. Из вершин №8 и №2 ведут пути только по неосвещенным коридорам в вершины №7, №5 и №1, 6 и т.д. Это приводит к построению дерева, приведенного на рисунке. Остаётся перебрать 6 вариантов, считывая последовательности справа налево. Истинный вариант: 01011 (выделен жирным).
01011