Задача 5. Робот-пылесос
Современные роботы-пылесосы очень умные. Например, они способны в своей памяти строить карту помещения, разбивать помещение на сектора и даже прогнозировать загрязнения каждого сектора. Сектора, закрашенные в чёрный цвет, недоступны для уборки. Там, вероятно, стоит диван, кресло или какое-то другое препятствие. Число на секторе — это прогнозируемое количество пыли. У робота-пылесоса, который отмечен на карте помещения рисунком, заканчивается заряд батареи, и пылесос может выполнить только X перемещений в соседний сектор. По какому маршруту лучше пройти роботу, чтобы собрать как можно больше пыли?
Карта помещения:
Робот-пылесос может передвигаться строго по свободным секторам (не покрашенным в чёрный цвет) и не может выезжать за пределы помещения. Если пылесос сталкивается с препятствием или стеной комнаты, то он останавливается.
Маршрут пылесоса необходимо записать в виде строки из символов «U», «D», «L», «R», где «U» обозначает перемещение на один сектор вверх, «D» — перемещение вниз, «L» — перемещение влево, «R» — перемещение вправо.
Например, при движении по маршруту «URR» робот-пылесос соберёт 5 единиц пыли, а при исполнении маршрута «RRU» соберёт 3 единицы пыли, затем столкнётся с препятствием и остановится.
Запишите маршрут движения робота-пылесоса, при котором он сможет собрать наибольшее количество пыли при заданных X. Ответы записывайте в виде последовательностей символов «U», «D», «L», «R» без пробелов и иных разделителей.
Ответ на Задачу 5.
Решение 1.
Решение основывается на переборе разных вариантов маршрутов, где мы стремимся набрать как можно больше пыли.
Маршруты легче искать в такой таблице, если закрасить сектора в разные цвета в зависимости от количества пыли. Это легко можно сделать в электронных таблицах: нужно переписать данные в таблицу, выделить её и применить «Условное форматирование» —> «Цветовые шкалы» —> «Цветовая шкала зелёный-жёлтый-красный». Теперь маленькие числа будут красными, а большие — зелёными. Такая таблица называется тепловой картой.
Тепловая карта помещения:
Найдём решение для X = 3:
В радиусе трёх секторов от робота-пылесоса самые большие числа — это 5, 4 и несколько троек. Попытаемся их объединить и найти маршрут, который позволит роботу собрать наибольшее количество пыли.
- LLL 1 + 3 + 4 = 8
- DRU 5 + 1 + 3 = 9
- RDL 3 + 1 + 5 = 9
Остальные маршруты позволят собрать намного меньше пыли То есть наилучший маршрут позволяет собрать 9 единиц пыли и будет иметь вид «DRU» или «RDL». Пример маршрута «RDL»:
Для нахождения ответа при X = 5, 7, 9 используем аналогичную логику. Определяем области секторов, где мы можем набрать больше всего пыли, и строим маршрут туда через сектора с наибольшими числами.
Для X = 5 маршрут «LLLUU» позволяет собрать 14 единиц пыли.
Для X = 7 маршрут «UULLLDD» позволяет собрать 20 единиц пыли.
Для X = 9 маршрут «DRRDRRRDD» позволяет собрать 27 единиц пыли.
Решение 2.
Ещё один способ решения — написать программу, которая переберёт все маршруты нужной длины и найдёт маршрут, позволяющий собрать больше всего пыли. Полный перебор можно реализовать через рекурсивный алгоритм поиска в глубину. Такое решение в данной задаче будет работать довольно быстро, потому что маршрут максимальной длины не очень длинный.
x, y = 2, 3 # начальная координата робота
n, m = 7, 9 # размеры помещения
# карта помещения. Препятствия заменены на -99,
# чтобы роботу было явно невыгодно туда ходить
field = [[ 3, 4, 1, 3, -99, 3, 2, 1, 6 ],
[ 3, -99, 1, 2, 1, 2, 2, 1, 1 ],
[ 4, 3, 1, 0, 3, -99, -99, 4, 3 ],
[ 1, 1, -99, 5, 1, 2, 2, 2, 3 ],
[ 2, 3, -99, 1, -99, 2, 2, 4, 1 ],
[ 4, 1, 4, 1, -99, 3, 3, -99, 1 ],
[ 2, 3, 2, 2, 1, 4, 2, -99, 9 ]]
# двумерный список, где мы будем отмечать сектора, по которым
# проехал робот-пылесос. 0 − не проехал, 1 − проехал
used = [ [0] * m for _ in range(n) ]
# из любого сектора можно проехать в одну из четырёх сторон (список направлений).
# 0. y - 1, x + 0 − движение вверх (U)
# 1. y + 1, x + 0 − движение вниз (D)
# 2. y, x - 1 − движение влево (L)
# 3. y, x + 1 − движение вправо (R)
d = [[ -1, 0], [1, 0], [0, -1], [0, 1]]
# функция, которая проверяет, находится ли робот-пылесос внутри помещения
def coord_ok(i, j):
return 0 < = i < n and 0 < = j < m
# функция рекурсивного перебора.
# i, j − текущая координата робота
# curEnergy − количество потраченного заряда
# curPoints − объём собранной пыли
# bp − путь, пройденный до текущей координаты
def dfs(i, j, curEnergy, curPoints, bp):
# если заряд закончился, заканчиваем движение
if curEnergy = = energy:
return curPoints, bp
maxPoints = 0
bestPath = ""
# отправим робота на 4 разные стороны и посмотрим,
# откуда он принесёт больше всего пыли.
for k in range(4):
i1 = i + d[k][0]
j1 = j + d[k][1]
if coord_ok(i1, j1):
x = field[i1][j1]
field[i1][j1] = 0
points, path = dfs(i1, j1, curEnergy + 1, curPoints + x, bp + str(k))
if points > maxPoints:
maxPoints = points
bestPath = path
field[i1][j1] = x
return maxPoints, bestPath
# переберём длины маршрутов и для каждого случая найдём маршрут,
# который позволит роботу собрать наибольшее количество пыли.
for i in 3, 5, 7, 9:
energy = i
a, b = dfs(x, y, 0, 0, "")
# заменим номера направлений на буквы.
print(b.replace("0", "U").replace("1", "D").replace("2", "L").replace("3", "R")) 