Олимпиадный тренинг

Задача . ТР03. Задание 18. Робот: стены и несколько конечных клеток


Задание выполняется с использованием прилагаемых файлов.

Квадрат разлинован на N × N клеток, где 1 < N < 30. Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз.

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

Перед каждым запуском в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это относится также к начальной и конечной клеткам маршрута.

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

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

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

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

Иллюстративный пример

Для поля 2 × 2 без внутренних стен с числами, приведёнными ниже, возможны маршруты 1 → 2 → 4 и 1 → 3 → 4.

12
34

Максимальная сумма в этом примере равна 8, минимальная — 7. Пример поясняет правила подсчёта; для выполнения задания используйте данные прилагаемого файла.

Запись ответа на платформе. Введите два числа в указанном в условии порядке, разделив их одним пробелом.