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