Задание №18

Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вверх или по диагонали вправо вверх. Шаг вправо разрешается сделать только в клетку с числом той же чётности, шаг вверх – только в клетку с числом другой чётности. Шаг по диагонали возможен всегда.

Необходимо перевести робота в правую верхнюю клетку поля. Определите максимальную сумму чисел в клетках, через которые можно провести такой маршрут. Определите также количество клеток поля, в которые робот не сможет попасть из-за ограничений на возможные переходы.

В ответе запишите два числа: сначала максимально возможное значение суммы входящих в маршрут чисел, затем количество недоступных клеток.

Исходные данные записаны в электронной таблице. Пример входных данных (для таблицы размером 4×4):

При указанных входных данных максимальное значение 147 получится при движении по маршруту 6 → 50 → 49 → 11 → 31. Недоступны для робота клетки с числами 61, 15, 12, 17, 53 – всего 5 клеток. В ответе в данном случае надо записать числа 147 и 5.