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

Исполнитель Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано натуральное число. Он может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Расход энергии на запуск робота равен числу, записанному в стартовой клетке. В дальнейшем расход энергии на шаг из одной клетки в другую равен абсолютной величине разности чисел, записанных в этих клетках. Определите минимальный и максимальный расход энергии при переходе робота из левой верхней клетки поля в правую нижнюю. В ответе запишите два числа: сначала минимальный расход энергии, затем – максимальный.
Пример входных данных:
При указанных входных данных минимальное значение получится при движении по маршруту 31 → 18 → 23 → 17 → 19 → 14 → 3. Расход энергии на этом пути равен 31 + (31–18) + (23–18) + (23–17 ) + (19–17) + (19–14) + (14–3) = 73. Максимальное значение получится при движении по маршруту 31 → 18 → 48 → 12 → 8 → 30 → 3, расход энергии в этом случае равен 163. Ответ: 73 163.
Исходные данные записаны в файле 18-170.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа – сначала минимальный расход энергии, затем – максимальный.