18_0366

Задание выполняется с использованием прилагаемого файла.

Квадрат разлинован на $16\times16$ клеток. Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю.

Квадрат ограничен внешними стенами. Между соседними клетками также могут быть внутренние стены. Сквозь стену Робот пройти не может.

В каждой клетке поля лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута.

Робот начинает движение в левой верхней клетке. В клетках, которые справа и снизу ограничены стенами, он не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток может быть несколько, включая правую нижнюю клетку поля.

Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм. В ответе укажите два числа — сначала максимальную сумму, затем минимальную.

Исходные данные представлены электронной таблицей, каждая ячейка которой соответствует клетке поля. Внутренние и внешние стены обозначены утолщёнными линиями.

Файлы к заданию:

• 18_0366.ods