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

Квадрат разлинован на N×N клеток (1 < N < 20). В правом верхнем углу квадрата стоит ладья. За один ход ладья может переместиться в пределах квадрата на любое количество клеток влево или вниз (вправо и вверх ладья ходить не может). Определите минимальную и максимальную сумму чисел в клетках, в которых может остановиться ладья при перемещении из правого верхнего угла в левый нижний. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные записаны в файле 18-99.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке квадрата.