Задание №18: Динамическое программирование (Робот в таблице)

*(Е. Джобс) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается на две клетки вправо, по команде вверх – на две клетки вверх. При попытке выхода за границу квадрата Робот телепортируется на противоположную сторону. Например, если из крайней правой клетки выполнить команду вправо, робот переместится во второй столбец этой же строки. Перед каждым запуском Робота в каждой клетке квадрата записано число от 1 до 99. Посетив клетку, Робот прибавляет к своему счету записанное в ней значение. После посещения клетки число в ней обнуляется. Определите максимальное и минимальное значение счета, который может набрать Робот, пройдя из левой нижней клетки в правую верхнюю.
Пример входных данных (для поля 3х3):
Исходные данные записаны в файле 18-152.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа – сначала максимальное значение, затем минимальное.