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

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