Задача: Робот-пылесос

Современные роботы-пылесосы очень умные. Например, они способны в своей памяти строить карту помещения, разбивать помещение на сектора и даже прогнозировать загрязнения каждого сектора. Сектора, закрашенные в чёрный цвет, недоступны для уборки. Там, вероятно, стоит диван, кресло или какое-то другое препятствие. Число на секторе это прогнозируемое количество пыли. У робота-пылесоса, который отмечен на карте помещения рисунком, заканчивается заряд батареи, и пылесос может выполнить только X перемещений в соседний сектор. По какому маршруту лучше пройти роботу, чтобы собрать как можно больше пыли?

Робот-пылесос может передвигаться строго по свободным секторам (не покрашенным в чёрный цвет) и не может выезжать за пределы помещения. Если пылесос сталкивается с препятствием или стеной комнаты, то он останавливается.
Маршрут пылесоса необходимо записать в виде строки из символов "U", "D", "L", "R", где "U" обозначает перемещение на один сектор вверх, "D" перемещение вниз, "L" перемещение влево, "R" перемещение вправо.
Например, при движении по маршруту "URR" робот-пылесос соберет 5 единиц пыли, а при исполнении маршрута "RRU" соберёт 3 единицы пыли, затем столкнётся с препятствием и остановится.
Запишите маршрут движения робота-пылесоса, при котором он сможет собрать наибольшее количество пыли при заданных X. Ответы записывайте в виде последовательностей символов "U", "D", "L", "R" без пробелов и иных разделителей.

Значение X	Маршрут
3
5
7
9

 

           

Ваш ответ: