Банк заданий
ЕГЭ по информатике Задание №18 Динамическое программирование в электронных таблицах, Другие случаи динамического программирования в электронных таблицах

Квадрат разлинован на $N * N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

В начальный момент Робот обладает запасом энергии, которая расходуется на движение по клеткам. Изначальный запас энергии Робота равен числу, записанному в стартовой клетке. Кроме обычных клеток также есть «заправочные станции» – это клетки, выделенные зелёным цветом. При посещении обычных клеток запас энергии Робота уменьшается на число, записанное в этих клетках; при посещении «заправочных станций» – увеличивается на записанное в них значение.

Определите максимальный и минимальный запас энергии, который может быть у Робота после перехода из левой верхней клетки в правую нижнюю клетку поля.

В ответе укажите два числа - сначала максимальное значение, затем минимальное.

Исходные данные представляют собой электронную таблицу размером $N * N$, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.

Пример входных данных

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/19488_18.xlsx