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

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