вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю пилоною. Квадрат ограничен внешними стенами. Между соседними клетками…
Вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю пилоною. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. В «угловых» клетках поля - тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых суми, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные' представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями. Пример входных данных 1 8 8 4 10 1 1 3 1 3 12 2 2 3 5 6
Пояснение и решение (пример для уровня средней школы)
Цель: определить максимальную и минимальную суммы монет, которую может собрать робот, начиная с левой верхней клетки и заканчивая на любой «угловой» конечной клетке (в примере внутренних стен нет, следовательно, конечной клеткой является нижняя правая клетка).
Данные примера Клетки 4×4, значения монет: 1 8 8 4 10 1 1 3 1 3 12 2 2 3 5 6
Так как внутренних стен нет, робот может двигаться только вправо или вниз, и путь заканчивается в нижней правой клетке (4,4). Нужно посчитать максимальную и минимальную суммы по всем возможным путям из (1,1) в (4,4).
- Максимальная сумма (динамическое программирование) Обозначим max[i][j] — максимальная сумма, которую можно набрать, добравшись до клетки (i, j).
Правило: max[i][j] = значение в клетке (i, j) + max( max[i-1][j], max[i][j-1] ), где недоступные соседи не учитываются.
Получаем таблицу max:
- 1 9 17 21
- 11 12 18 24
- 12 15 30 32
- 14 18 35 41
Итоговая максимальная сумма: 41.
- Минимальная сумма (аналогично, но минимизация) Обозначим min[i][j] — минимальная сумма до клетки (i, j).
Правило: min[i][j] = значение в клетке (i, j) + min( min[i-1][j], min[i][j-1] ).
Получаем таблицу min:
- 1 9 17 21
- 11 10 11 14
- 12 13 23 16
- 14 16 21 22
Итоговая минимальная сумма: 22.
Итог Максимальная сумма: 41 Минимальная сумма: 22
Примеры путей (для иллюстрации)
Максимальная путь: (1,1) → (1,2) → (1,3) → (2,3) → (3,3) → (4,3) → (4,4) Монеты: 1 + 8 + 8 + 1 + 12 + 5 + 6 = 41
Минимальная путь: (1,1) → (1,2) → (2,2) → (2,3) → (2,4) → (3,4) → (4,4) Монеты: 1 + 8 + 1 + 1 + 3 + 2 + 6 = 22
Ответ в формате: сначала максимальная сумма, затем минимальная. 41 22
