Задание 18 ЕГЭ по информатике

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

Перед каждым запуском Робота в каждой клетке квадрата указан бонус за посещение в размере от 1 до 100. Посетив клетку, Робот получает бонус за её посещение; это также относится к начальной и конечной точке маршрута Робота.

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

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

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

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

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