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

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

В каждой клетке лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету. В «угловых» клетках (ограниченных стенами справа и снизу) Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных точек может быть несколько, включая правую нижнюю клетку.

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

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

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