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

Решение.
В исходном файле поле 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. Дальше применяем те же правила с учётом стен.
В табличном редакторе удобно создать две рабочие таблицы той же формы и сохранить разметку стен. В формулах используем значения только допустимых предшественников. Нельзя ставить ноль в недостижимую клетку и затем учитывать его при поиске минимума: это создало бы несуществующий дешёвый путь.
В исходном поле конечные клетки: N11, H17, S18, N20, T20. У каждой закрыты оба разрешённых выхода — вправо и вниз. Все они достижимы из A1. Сравниваем итоговые значения именно в этих клетках; промежуточную клетку со свободным выходом считать концом маршрута нельзя.
После заполнения таблиц получаем:

Наибольшая из итоговых сумм равна 2491, наименьшая — 522. Они могут относиться к разным конечным клеткам.
Проверка достижимости максимума. Один подходящий маршрут:
A1 → B1 → C1 → D1 → E1 → F1 → F2 → F3 → F4 → F5 → F6 → G6 → G7 → G8 → G9 → G10 → H10 → I10 → I11 → J11 → J12 → J13 → K13 → L13 → M13 → N13 → O13 → O14 → O15 → O16 → O17 → O18 → O19 → O20 → P20 → Q20 → R20 → S20 → T20.
Сумма его монет: 23 + 11 + 82 + 85 + 88 + 99 + 93 + 62 + 45 + 59 + 83 + 72 + 88 + 56 + 80 + 70 + 76 + 63 + 85 + 73 + 72 + 72 + 79 + 74 + 74 + 82 + 87 + 43 + 76 + 57 + 91 + 82 + 91 + 68 + 6 + 6 + 17 + 7 + 14 = 2491.
Проверка достижимости минимума. Один подходящий маршрут:
A1 → A2 → A3 → A4 → A5 → A6 → A7 → A8 → A9 → A10 → A11 → A12 → A13 → A14 → A15 → A16 → A17 → B17 → C17 → D17 → E17 → F17 → G17 → H17.
Сумма его монет: 23 + 32 + 20 + 35 + 7 + 30 + 22 + 15 + 16 + 29 + 34 + 21 + 12 + 24 + 34 + 10 + 18 + 18 + 26 + 24 + 14 + 25 + 8 + 25 = 522.
В обоих маршрутах каждый следующий адрес отличается на один столбец вправо или на одну строку вниз, и ни один переход не пересекает толстую стену. Последние клетки закрыты справа и снизу, поэтому маршруты завершены по условию.
Рекурсия перебрала оба возможных последних хода в каждой из 400 клеток. Следовательно, большее максимальное или меньшее минимальное значение получить нельзя; приведённые маршруты достигают найденных границ.
Время и память для двух таблиц пропорциональны N². Порядок чисел в ответе: сначала максимум, затем минимум.
Ответ: 2491 522.