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

*Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого лежит монета достоинством от 1 до 100. За один ход Робот может переместиться на одну клетку вправо, вверх или по диагонали вправо вверх. Шаг вправо разрешается сделать только в клетку, где лежит монета с достоинством той же чётности, шаг вверх – только в клетку с монетой другой чётности. Шаг по диагонали возможен всегда. Необходимо перевести Робота в правую верхнюю клетку поля. Определите максимальную денежную сумму, которую может собрать Робот, и количество клеток поля, недоступных для Робота.
Пример входных данных:
Оптимальный маршрут проходит через клетки с монетами достоинством 13, 33, 50, 74, 66 (сумма 236). Все клетки, выделенные фоном, недоступны для Робота из-за ограничений.
Исходные данные записаны в файле 18-167.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа: максимальную денежную сумму, которую может собрать Робот, затем количество клеток поля, недоступных Роботу.