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

Исполнитель Робот стоит в правом нижнем углу поля, разлинованного на клетки. Он может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: влево или вверх. По команде влево Робот перемещается в соседнюю левую клетку; по команде вверх – в соседнюю верхнюю. В некоторых клетках записано число –1, в эти клетки роботу заходить нельзя. Такие клетки для удобства выделены фоном. В остальных клетках записаны положительные числа. Клетка, из которой робот не может сделать допустимого хода (слева и сверху находятся границы поля или запрещённые клетки), называется финальной. На поле может быть несколько финальных клеток. В начальный момент робот обладает некоторым запасом энергии. Расход энергии на запуск робота равен числу, записанному в стартовой клетке. В дальнейшем расход энергии на шаг из одной клетки в другую равен абсолютной величине разности чисел, записанных в этих клетках. Выполните два задания:
Задание 1. Определите минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки.
Задание 2. Определите минимальный начальный запас энергии, который позволит роботу пройти любым допустимым маршрутом до любой финальной клетки.
Исходные данные записаны в файле 18-208.xls в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа: сначала ответ на задание 1, потом – ответ на задание 2.