Задание №18Информационные модели и структуры данныхЕГЭ по информатике

Квадрат разлинован на $N \times N$ клеток ($1 < N < 25$). Исполнитель Робот перемещается по клеткам, выполняя за одно действие одну из двух команд: вправо или вниз. При попытке выхода за границу квадрата Робот разрушается. Между соседними клетками могут быть внутренние стены, сквозь которые Робот пройти не может. В каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету; это относится к начальной и конечной клетке маршрута.

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

Исходные данные представляют собой электронную таблицу размером $N \times N$, каждая ячейка которой соответствует клетке квадрата.