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

Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вниз, по диагонали вправо-вниз или по диагонали влево-вниз. Числа показывают расход энергии робота на прохождение клетки.
Определите максимальный расход энергии при переходе робота в правую нижнюю клетку поля и количество клеток с нечётными числами, через которые робот проходит на пути с максимальным расходом энергии. В ответе запишите два числа: сначала максимальный расход энергии, затем – количество пройденных клеток с нечётными значениями.
Пример входных данных (для таблицы размером 4×4):
При указанных входных данных максимальный расход получится при движении по маршруту 26 + 44 + 18 + 11 + 89 + 39 + 46 + 38 + 12 + 68 = 391. При этом робот проходит через 3 клетки с нечётными числами (11, 89, 39). В ответе в данном случае надо записать числа 391 и 3.
Исходные данные записаны в файле 18-154.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке поля. В ответе запишите два числа: сначала максимальный расход энергии, затем – количество пройденных клеток с нечётными значениями.