Задача #3964

(Д. Бахтиев) Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. В начальный момент Робот обладает запасом энергии, которая расходуется на движение по клеткам. Изначальный запас энергии Робота равен числу, записанному в стартовой клетке. Кроме обычных клеток также есть «волшебные удвоители» – это клетки, выделенные жёлтым цветом. При посещении обычных клеток запас энергии Робота уменьшается на число, записанное в этих клетках; при посещении «волшебных удвоителей» – текущий запас энергии увеличивается в 2 раза.

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