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