Современные роботы‑пылесосы очень умные. Например, они способны в своей памяти строить карту помещения, разбивать помещение на сектора и даже прогнозировать загрязнения каждого…

Современные роботы‑пылесосы очень умные. Например, они способны в своей памяти строить карту помещения, разбивать помещение на сектора и даже прогнозировать загрязнения каждого сектора. Сектора, закрашенные в чёрный цвет, недоступны для уборки. Там, вероятно, стоит диван, кресло или какое‑то другое препятствие. Число на секторе — это прогнозируемое количество пыли. У робота‑пылесоса, который отмечен на карте помещения рисунком, заканчивается заряд батареи, и пылесос может выполнить только X перемещений в соседний сектор. По какому маршруту лучше пройти роботу, чтобы собрать как можно больше пыли? Робот‑пылесос может передвигаться строго по свободным секторам (не покрашенным в чёрный цвет) и не может выезжать за пределы помещения. Если пылесос сталкивается с препятствием или стеной комнаты, то он останавливается. Маршрут пылесоса необходимо записать в виде строки из символов «U», «D», «L», «R», где «U» обозначает перемещение на один сектор вверх, «D» — перемещение вниз, «L» — перемещение влево, «R» — перемещение вправо. Например, при движении по маршруту «URR» робот‑пылесос соберёт 5 единиц пыли, а при исполнении маршрута «RRU» соберёт 3 единицы пыли, затем столкнётся с препятствием и остановится. Запишите маршрут движения робота‑пылесоса, при котором он сможет собрать наибольшее количество пыли при заданных X . Ответы записывайте в виде последовательностей символов «U», «D», «L», «R» без пробелов и иных разделителей. Значение X Маршрут 3 Ответ 5 Ответ 7 Ответ 9 Ответ