Задание №18: Динамическое программирование (Робот в таблице)

(В. Шубинкин) Виртуальный исполнитель Варя живёт на клеточном поле размером N×M клеток. Исполнитель может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Варя перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Поле ограничено внешними стенами. Между соседними клетками поля также могут быть внутренние стены, сквозь стену Варя пройти не может. На поле имеется голубая клетка, с которой исполнитель может телепортироваться в любую клетку правее и/или ниже голубой в пределах поля. В каждой клетке поля записано целое число, не превышающее по модулю 100. Исполнитель суммирует числа в клетках, которые посетил.
Исходные данные записаны в файле 18-141.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке поля. Внутренние и внешние стены обозначены утолщёнными линиями. Определите минимальную и максимальную сумму, которую может получить исполнитель, пройдя из верхней левой клетки в правую нижнюю. В ответе укажите два числа – сначала минимальную сумму, затем максимальную.
Пример входных данных для поля 5×5:

На таком поле Варя из клетки B3 может перейти в любую клетку диапазона B3:E5, кроме самой клетки B3 (стены не препятствуют телепортации). Для приведённого примера ответом будут числа -20 и 3.