Задача #6024

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

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

Исходные данные записаны в электронной таблице размером N x N, каждая ячейка которых соответствует клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.

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

Для указанных входных данных ответом должна быть пара чисел:

22 41