Квадрат разлинован на 5 × 5 клеток. Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. Квадрат ограничен внешними стенами; между соседними клетками могут быть внутренние стены, сквозь которые Робот пройти не может. В каждой клетке лежит монета достоинства, указанного в таблице. Посещая клетку, Робот забирает монету, в том числе из начальной и конечной клеток.
В «угловых» клетках — тех, которые справа и снизу ограничены стенами, — Робот не может продолжать движение, поэтому накопленная сумма считается итоговой; таких клеток может быть несколько.
Значения в клетках (строки сверху вниз, столбцы слева направо):
2 5 3 6 1
4 1 7 2 5
3 6 2 4 7
5 2 6 1 3
1 4 3 5 2
Внутренние стены (между клетками): (1, 2)–(1, 3); (1, 4)–(2, 4); (2, 3)–(2, 4); (3, 4)–(4, 4); (4, 2)–(4, 3).
Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа: сначала максимальную сумму, затем минимальную.
Запишите два…
В «угловых» клетках — тех, которые справа и снизу ограничены стенами, — Робот не может продолжать движение, поэтому накопленная сумма считается итоговой; таких клеток может быть несколько.
Значения в клетках (строки сверху вниз, столбцы слева направо):
2 5 3 6 1
4 1 7 2 5
3 6 2 4 7
5 2 6 1 3
1 4 3 5 2
Внутренние стены (между клетками): (1, 2)–(1, 3); (1, 4)–(2, 4); (2, 3)–(2, 4); (3, 4)–(4, 4); (4, 2)–(4, 3).
Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа: сначала максимальную сумму, затем минимальную.
Запишите два…
Подсказка 1. В каждой клетке запишите пару значений: наибольшую и наименьшую сумму, с которой в неё можно прийти.
Подсказка 2. Клетка недостижима, если оба входа в неё закрыты стенами; значения складываются с числом в самой клетке, включая стартовую.
Подсказка 3. Заполняйте таблицу построчно слева направо и сверху вниз, затем выберите угловые клетки (справа и снизу стены).
Разбор.
Приём — динамическое программирование по клеткам. Заполняем таблицу значений (максимум и минимум для каждой достижимой клетки), учитывая стены. Итоговые (угловые) клетки — те, у которых закрыты и правый, и нижний переходы. Среди них максимум равен 33, минимум — 27.
Ответ: 33 27.
Ответ.
33 27