Задание EGEINF94107F: Оптимальный маршрут по клетчатому полю

Решение.
Откроем приложенную электронную таблицу. Исходные числа занимают диапазон A1:T20: поле имеет размер 20 × 20. Начинаем в A1 и движемся только вправо или вниз. Число в каждой посещённой клетке, включая начало и финиш, прибавляется к сумме.
Финиш разрешён в любой угловой клетке в смысле условия: из неё нельзя сделать ни шаг вправо, ни шаг вниз. Учитываем внутренние стены и внешнюю границу поля. Останавливаться в произвольной промежуточной клетке нельзя.
В исходном поле найдено 50 внутренних границ между соседними клетками, через которые проход запрещён.
Будем хранить для каждой достижимой клетки две величины: L — наименьшую сумму от A1 до неё, H — наибольшую. Для A1 обе величины равны числу в самой A1: 38.
В любую другую клетку можно прийти только из соседней слева или сверху. Переход слева разрешён, если нет стены между этими клетками; переход сверху — если нет стены над текущей клеткой. Недостижимого соседа не используем.
Если оба входа разрешены, прибавим число текущей клетки к меньшей из двух величин L и к большей из двух величин H. Если допустимый вход один, берём только его. Если нет ни одного, помечаем клетку «нет пути», а не нулём.
Это динамическое программирование: любой путь в текущую клетку заканчивается одним из допустимых входов. Поэтому выбор лучшего пути до предшественника перебирает все возможности последнего шага. Обрабатывая строки сверху вниз, а клетки в строке слева направо, получаем точные минимум и максимум для всего поля.
Для расчёта в редакторе таблиц создадим под исходными числами блок максимумов с началом в A22. В A22 введём =A1. Например, значение для B2 окажется в B23: при двух допустимых входах формула имеет вид =B2+МАКС(A23;B22). Если вход перекрыт стеной или ведёт из недостижимой клетки, соответствующую ссылку исключаем. Начальную клетку общей формулой не заменяем.
Первую строку заполняем только по входу слева, первый столбец — только по входу сверху. После каждой стены отдельно проверяем достижимость. Для минимумов создадим такой же блок, заменив МАКС на МИН и сохранив все ограничения переходов. Нельзя протянуть общую формулу через стены без исправления ссылок.
Контрольные значения начала таблицы:

Значения в разрешённых конечных клетках:

Среди достижимых конечных клеток наименьшее значение L равно 695, наибольшее значение H равно 2061. Они могут достигаться в разных тупиках.
Проверка. Восстановим оба оптимальных маршрута, каждый раз выбирая предшественника, давшего записанную сумму. Ниже указаны посещённые столбцы по строкам; диапазон включает оба края. Между строками спускаемся в том столбце, в котором закончился предыдущий отрезок. Знак «—» означает, что маршрут завершился раньше.

Все переходы этих маршрутов разрешены. Суммы чисел исходного файла дают 695 и 2061; начальная и конечная клетки учтены ровно один раз. Таблица динамического программирования доказывает, что меньшая и большая суммы невозможны.
По условию сначала записываем максимум, затем минимум.
Ответ: 2061 695.