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

(Е. Джобс) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. На каждое перемещение Робот тратит 10 единиц заряда батареи. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь сте-ну Робот пройти не может. В каждой клетке установлена зарядная станция, которая может повысить заряд робота не более, чем на число единиц, указанное в этой ячейке. Заряд робота не может превысить 100 единиц. Если перед выполнением команд вправо или вниз процент заряда батареи робота меньше 10 единиц, то выполнение данных команд невозможно.
В начальный момент уровень заряда равен значению, указанному в левой верхней клетке поля. На зарядку робот тратит 5 минут, на выполнение одной команды вниз или вправо – 1 минуту. Определите минимальное количество минут, за которое робот сможет преодолеть лабиринт – добраться до правой нижней клетки.
Исходные данные для Робота записаны в файле 18-136.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке квадрата. Пример входных данных:
Для указанных входных данных ответом является число 16 (ВНИЗ-ВНИЗ-(Зарядка)-ВНИЗ-(Зарядка)-ВПРАВА-ВПРАВО-ВПРАВО).