(№ 3708) (А.М. Кабанов) Квадрат разлинован на N×N клеток (1 < N < 20). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд:
влево или
вверх. По команде
влево Робот перемещается на
любое количество клеток влево, по команде
вверх – на любое количество клеток вверх. При попытке пересечь
границы (внутренние, обозначенные жирными линиями, или границы квадрата) Робот разрушается. В каждой клетке квадрата указана плата за посещение в размере от 1 до 100. Остановившись в клетке, Робот платит за её посещение; это также относится к начальной и конечной точке маршрута Робота. Определите минимальную и максимальную денежную сумму, которую заплатит Робот, пройдя из правой нижней клетки в левую верхнюю. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные для Робота записаны в файле
18-90.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке квадрата.