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

(М. Коротков, г. Челябинск) Квадрат разлинован на N×N клеток (1 < N < 20). Исполнитель Пассажир на Самокатике перемещается из левой верхней клетки в правую нижнюю, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо он перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке выхода за границу квадрата Самокатик разваливается на части и прекращает движение. В каждой клетке квадрата записано целое число в диапазоне от -100 до 100. Самокатик – электрический; начальный уровень заряда его батареи указан в левой верхней клетке квадрата. При посещении очередной клетки уровень заряда батареи Самокатика изменяется на указанное в ней значение, но не может стать меньше 0 или больше 100. Это также относится к конечной клетке маршрута. Всякий раз, когда уровень заряда батареи Самокатика опускается до нуля, Пассажир спешивается и тащит его на себе.
Определите максимально возможный уровень заряда батареи Самокатика в конечной клетке, если Пассажиру на протяжении всего маршрута:
    A) запрещено спешиваться;
    B) разрешено спешиваться.
Исходные данные для Робота записаны в файле 18-107.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала ответ на вопрос А, затем – ответ на вопрос B.