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

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

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

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

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

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

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

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