18_0370

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

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

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

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

Робот может начать движение в любой из трёх клеток C10, G6 и K2, выделенных синим цветом. Закончить движение он должен в одной из клеток G16, L11 и P7, выделенных зелёным цветом.

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

В ответе укажите два числа — сначала максимальную сумму, затем минимальную.

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

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

• 18_0370.ods