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

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

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

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

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

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