Задача #6035

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

При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата записана величина вознаграждения от 1 до 100. Попав в клетку после хода, Робот получает указанное в ней вознаграждение. Это также относится к начальной и конечной клетке маршрута Робота.

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

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