Задача 4. Квест Новый квест, в котором участники должны выбраться с территории проведения, представляет собой прямоугольник из 16 комнат в виде квадрата 4 × 4. Каждая комната имеет четыре двери, ведущие в соседние комнаты, из комнат на краю прямоугольника двери ведут наружу, через эти двери можно покинуть территорию проведения квеста. В начале квеста в каждой комнате находится по человеку, а все двери заперты. После начала квеста организаторы дистанционно открывают в каждой комнате запирающий механизм одной из четырёх дверей. Теперь человек, находящийся в этой комнате, может открыть эту дверь и перейти в соседнюю комнату, через другие три двери выйти из этой комнаты нельзя. При этом может оказаться так, что дверь, соединяющая две комнаты, будет отпираться с одной стороны, тогда пройти через эту дверь можно только с той стороны, с которой она будет открываться, проходить через дверь в обратном направлении нельзя, если в соседней комнате будет отперта не эта дверь, а какая-то другая. Если комната находится на краю территории и из этой комнаты открыта дверь наружу, то, пройдя через эту дверь, участник навсегда покидает территорию квеста. После начала квеста и отпирания дверей участники начинают перемещаться между комнатами. Каждый участник перемещается в соседнюю открытую комнату и продолжает перемещаться до тех пор, пока не покинет территорию квеста. Однако возможна ситуация, когда некоторые участники будут бесконечно перемещаться между комнатами и никогда не выйдут наружу. Разработчки квеста попросили Вас составить такой план отпирания дверей, при котором ровно 7 человек из 16 смогут выбраться наружу с территории квеста. При этом Вам необходимо минимизировать количество дверей, которые будут открыты из крайних комнат наружу (тех дверей, через которые участники будут покидать территорию квеста). Ответ на эту задачу нужно записать в виде плана территории квеста, состоящего из 4 строк, в каждой строке должно быть ровно 4 символа из следующего числа возможных. U: дверь в верхнюю по данному плану комнату. D: дверь в нижнюю комнату. L: дверь в левую комнату. R: дверь в правую комнату. Например, рассмотрим следующий план квеста, в котором 8 комнат: RDRR ULRR Этот план соответствует следующему рисунку.
Стрелками обозначены открытые двери, точками помечены комнаты, обитатели которых выйдут из квеста.
В этом примере наружу выходят 4 человека из 8. Вам необходимо составить план квеста из 4 рядов по 4 комнаты, в котором наружу выходят 7 человек из 16.