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

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

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

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

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