№431542037
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из команд: вправо или вниз. Робот начинает движение в левой верхней клетке квадрата. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
В начальный момент Робот обладает запасом энергии, которая расходуется на движение по клеткам. Расход энергии на прохождение каждой клетки, включая стартовую и конечную, равен числу, записанному в этой клетке.
Клетка, из которой Робот не может сделать допустимого хода (справа и снизу стены), называется финальной. На поле может быть несколько финальных клеток.
.
Определите минимальный начальный запас энергии, который позволит Роботу добраться до какой-нибудь финальной клетки.
.
Определите минимальный начальный запас энергии, который позволит Роботу добраться до любой финальной клетки (для каждой финальной клетки Робот выбирает самый экономный путь).
В обоих заданиях энергии должно хватить и на прохождение финальной клетки.
В ответе запишите два числа: сначала ответ на
, затем ответ на
.
Исходные данные представляют собой электронную таблицу размером N × N (в файле N = 17), каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.