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

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