Светофоростояние II (ОКД НТИ 19/20 :: ИЭС)
Легенда
После успешного выступления на конференции вы были приглашены на энергетический форум. Но путь к бизнес-центру, где он проходит, лежит через оживлённый городской район, дороги которого красиво выстроены в виде прямоугольной сетки, каждое из пересечений которого является регулируемым перекрёстком. Как и в прошлой задаче, вы знаете временные промежутки, в течение которых на каждом из них загорается красный или зелёный сигнал, причём зелёный горит только в одном из направлений одновременно — по вертикали или по горизонтали. Как промежутки соотносятся между светофорами во времени — неизвестно.
В отличие от прямой дороги, при движении по сетке можно самому выбирать наиболее оптимальное направление движения, чем вы и решили воспользоваться. На основе информации о светофорах составьте маршрут проезда по дорожной сетке с минимальным временем ожидания зелёного сигнала, начиная выездом с левого верхнего перекрёстка, заканчивая заездом на нижний правый.
Перемещения мимо светофора и между ними в расчёт не входят. Сам левый верхний перекрёсток не учитывать, его вы сразу пересекаете на зелёный сигнал. Маршрут заканчивается пересечением светофора на нижнем правом перекрёстке.
В данной задаче используются наиболее простые регулируемые перекрёстки — заезд на них разрешён в направлении зелёного сигнала, после этого допустимо выезжать в любом направлении. Маршрут проезда указывает на перемещения между перекрёстками и должен заканчиваться заездом на последний перекрёсток (направление выезда с него не имеет значения).