Робот и монеты

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот перемещается по клеткам, за один ход выполняя одну из двух команд: вправо или вниз (вправо — в соседнюю правую клетку, вниз — в соседнюю нижнюю). Квадрат ограничен внешними стенами, между соседними клетками могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой, это относится и к начальной, и к конечной клеткам маршрута. В «угловых» клетках поля (там, где справа и снизу ограничены стенами) Робот продолжать движение не может, поэтому накопленная сумма считается итоговой. Таких конечных клеток может быть несколько, в том числе правая нижняя. При разных запусках итоговые суммы могут быть разными. Определите максимальную и минимальную суммы, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе запишите два числа через пробел: сначала максимальную сумму, затем минимальную. Исходные данные лежат в электронной таблице N × N: каждая ячейка соответствует клетке квадрата, внутренние и внешние стены нарисованы утолщёнными границами ячеек.

Источник: ФИПИ (Демо), № 31515

Скачать файл: task_31515_A.ods. Решай в Excel или LibreOffice.