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

Решение.
В исходном файле поле 20 × 20, то есть диапазон A1:T20. Число в клетке — стоимость её монеты. Сумма включает начальную A1 и конечную клетку. Перемещаться можно только вправо или вниз через стороны без толстой стены.
Будем хранить для каждой достижимой клетки C две величины: M(C) — наибольшую сумму на пути из A1 в C, m(C) — наименьшую. Значение монеты в самой клетке обозначим a(C). Недостижимую клетку помечаем отдельно и не подставляем её в минимум или максимум.
Начальное значение: M(A1) = m(A1) = a(A1) = 23. У A1 нет предшествующего хода, поэтому её монета учитывается ровно один раз.
В любую другую клетку можно прийти только из соседней клетки слева или сверху. Левый предшественник допустим, если он достижим и между ним и текущей клеткой нет стены. Верхний проверяем так же. Стена справа или снизу от текущей клетки запрещает последующий ход, а не приход в эту клетку.
Если допустимых предшественников два, M(C) = a(C) + max(M(слева), M(сверху)), а m(C) = a(C) + min(m(слева), m(сверху)). Если предшественник один, к его сумме просто добавляем монету a(C). Если нет ни одного, клетка недостижима.
Заполняем значения построчно сверху вниз и слева направо. К моменту обработки клетки оба возможных предшественника уже обработаны. Любой путь в клетку заканчивается одним из этих ходов; добавление одинаковой монеты сохраняет порядок сумм. Поэтому рекурсия даёт точные максимум и минимум, а не только оценку.
Например, B1 можно достичь только из A1: M(B1) = m(B1) = 23 + 11 = 34. Аналогично M(A2) = m(A2) = 23 + 32 = 55.
В B2 оба входа открыты. M(B2) = 14 + max(34, 55) = 69; m(B2) = 14 + min(34, 55) = 48. Дальше применяем те же правила с учётом стен.
В табличном редакторе удобно создать две рабочие таблицы той же формы и сохранить разметку стен. В формулах используем значения только допустимых предшественников. Нельзя ставить ноль в недостижимую клетку и затем учитывать его при поиске минимума: это создало бы несуществующий дешёвый путь.
В исходном поле конечные клетки: K14, S14, Q20, T20. У каждой закрыты оба разрешённых выхода — вправо и вниз. Все они достижимы из A1. Сравниваем итоговые значения именно в этих клетках; промежуточную клетку со свободным выходом считать концом маршрута нельзя.
После заполнения таблиц получаем:

Наибольшая из итоговых сумм равна 2361, наименьшая — 907. Они могут относиться к разным конечным клеткам.
Проверка достижимости максимума. Один подходящий маршрут:
A1 → B1 → C1 → D1 → E1 → F1 → G1 → H1 → I1 → J1 → K1 → L1 → L2 → L3 → L4 → L5 → L6 → L7 → L8 → L9 → L10 → L11 → L12 → L13 → L14 → L15 → L16 → L17 → M17 → N17 → O17 → O18 → O19 → O20 → P20 → Q20.
Сумма его монет: 23 + 11 + 82 + 85 + 88 + 99 + 59 + 75 + 56 + 80 + 93 + 83 + 80 + 36 + 71 + 52 + 62 + 63 + 48 + 72 + 69 + 70 + 77 + 74 + 66 + 85 + 82 + 24 + 57 + 95 + 91 + 82 + 91 + 68 + 6 + 6 = 2361.
Проверка достижимости минимума. Один подходящий маршрут:
A1 → A2 → A3 → A4 → A5 → A6 → A7 → A8 → A9 → A10 → A11 → A12 → A13 → A14 → A15 → A16 → A17 → B17 → B18 → C18 → D18 → E18 → F18 → G18 → H18 → I18 → J18 → K18 → L18 → M18 → N18 → O18 → P18 → P19 → P20 → Q20.
Сумма его монет: 23 + 32 + 20 + 35 + 7 + 30 + 22 + 15 + 16 + 29 + 34 + 21 + 12 + 24 + 34 + 10 + 18 + 18 + 19 + 68 + 7 + 15 + 24 + 24 + 22 + 14 + 18 + 25 + 18 + 73 + 66 + 82 + 5 + 15 + 6 + 6 = 907.
В обоих маршрутах каждый следующий адрес отличается на один столбец вправо или на одну строку вниз, и ни один переход не пересекает толстую стену. Последние клетки закрыты справа и снизу, поэтому маршруты завершены по условию.
Рекурсия перебрала оба возможных последних хода в каждой из 400 клеток. Следовательно, большее максимальное или меньшее минимальное значение получить нельзя; приведённые маршруты достигают найденных границ.
Время и память для двух таблиц пропорциональны N². Порядок чисел в ответе: сначала максимум, затем минимум.
Ответ: 2361 907.