18.06 Прочие прототипы

Задание выполняется с использованием прилагаемых файлов

Квадрат разлинован на * клеток. Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх - в соседнюю верхнюю. При попытке выхода за границу квадрата Робот умирает. В квадрате могут быть ямы (помечены красным). Попадая в ямку Робот не может из нее выбраться и от горя ломается. В квадрате есть клетки, помеченные зеленым, в них сидят котики. Робот очень любит котиков, он старается пройти через эти клетки, чтобы погладить их. Первостепенная задача – погладить как можно больше котиков. К сожалению, котики расположены в таблице так, что робот не сможет погладить всех котиков, но он попытается погладить как можно большее количество котиков.

Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от до . Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.

При условии, что Робот погладил максимально возможное количество котиков и не упал в яму, определите максимальную денежную сумму, которую может собрать Робот. В ответ запишите одно число - максимальную сумму, которую может собрать Робот.