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

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

В каждой клетке лежит монета достоинством от 1 до 100. Робот собирает монеты со всех посещённых клеток, включая начальную и конечную.

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

Найдите максимальную и минимальную суммы среди всех возможных итоговых накоплений. В ответе укажите два числа через пробел: сначала максимум, затем минимум.

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