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

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

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

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

В ответе укажите два числа: сначала максимальную сумму, затем минимальную.

---