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

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

Для таких данных ответом будут числа 7 и 1 (см. карту движения исполнителя на рисунке справа).