Задача #3545

(В. Лашин) Олег на Хэллоуин собирает конфеты. Он ходит в разные дома и просит сладости. Информацию о том, сколько можно получить конфет в каждом из домов занесена в квадрат разлинованованный на N × N клеток (1 < N < 30). Олег может перемещаться по клеткам квадрата, выполняя за одно перемещение одно из двух действий: пройти вправо или вниз. По команде вправо Олег перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Олег пройти не может.

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

В «угловых» клетках поля - тех, которые справа и снизу ограничены стенами, Олег не может продолжать движение, поэтому накопленная сумма конфет считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.

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

В ответе укажите два числа - сначала количество домов для максимальной суммы, затем для минимальной.

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