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

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