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

*(Г. Золотухин) Квадрат разлинован на N×N клеток (1 < N < 20). В каждой клетке находится некоторое количество монет, от 1 до 100. Исполнитель «Конь» движется с левой линии в правую линию. т. е. он может стартовать из любой клетки первого столбца и закончить маршрут в любой клетке последнего столбца таблицы. С каждой посещённой клетки исполнитель забирает с собой половину монет, если количество монет нечётное, то округление происходит в большую сторону.
Исполнитель может двигаться «ходом коня»: на две клетки вправо и на одну вверх или вниз, или на одну клетку вправо и на две клетки вверх или вниз. Определите максимальную и минимальную суммы, которые может собрать исполнитель.
Пример входных данных (для таблицы размером 5×5):
Для данного примера максимальная сумма получается при проходе коня по клеткам со значениями 54, 98, 46, 75 и 55; эта сумма равна 27+49+23+38+28=165. Минимальная сумма получается при проходе коня по клеткам со значениями 16, 46 и 15; эта сумма равна 8+23+8=39. Ответ: 165 39.
Исходные данные записаны в файле 18-162.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке поля. В ответе запишите два числа: сначала максимальную сумму, затем минимальную.