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

Решение.
В исходном файле поле 20 × 20, то есть диапазон A1:T20. Число в клетке — стоимость её монеты. Сумма включает начальную A1 и конечную клетку. Перемещаться можно только вправо или вниз через стороны без толстой стены.
Будем хранить для каждой достижимой клетки C две величины: M(C) — наибольшую сумму на пути из A1 в C, m(C) — наименьшую. Значение монеты в самой клетке обозначим a(C). Недостижимую клетку помечаем отдельно и не подставляем её в минимум или максимум.
Начальное значение: M(A1) = m(A1) = a(A1) = 8. У A1 нет предшествующего хода, поэтому её монета учитывается ровно один раз.
В любую другую клетку можно прийти только из соседней клетки слева или сверху. Левый предшественник допустим, если он достижим и между ним и текущей клеткой нет стены. Верхний проверяем так же. Стена справа или снизу от текущей клетки запрещает последующий ход, а не приход в эту клетку.
Если допустимых предшественников два, M(C) = a(C) + max(M(слева), M(сверху)), а m(C) = a(C) + min(m(слева), m(сверху)). Если предшественник один, к его сумме просто добавляем монету a(C). Если нет ни одного, клетка недостижима.
Заполняем значения построчно сверху вниз и слева направо. К моменту обработки клетки оба возможных предшественника уже обработаны. Любой путь в клетку заканчивается одним из этих ходов; добавление одинаковой монеты сохраняет порядок сумм. Поэтому рекурсия даёт точные максимум и минимум, а не только оценку.
Например, B1 можно достичь только из A1: M(B1) = m(B1) = 8 + 16 = 24. Аналогично M(A2) = m(A2) = 8 + 33 = 41.
В B2 оба входа открыты. M(B2) = 15 + max(24, 41) = 56; m(B2) = 15 + min(24, 41) = 39. Дальше применяем те же правила с учётом стен.
В табличном редакторе удобно создать две рабочие таблицы той же формы и сохранить разметку стен. В формулах используем значения только допустимых предшественников. Нельзя ставить ноль в недостижимую клетку и затем учитывать его при поиске минимума: это создало бы несуществующий дешёвый путь.
В исходном поле конечные клетки: F8, L9, P20, T20. У каждой закрыты оба разрешённых выхода — вправо и вниз. Все они достижимы из A1. Сравниваем итоговые значения именно в этих клетках; промежуточную клетку со свободным выходом считать концом маршрута нельзя.
После заполнения таблиц получаем:

Наибольшая из итоговых сумм равна 2476, наименьшая — 436. Они могут относиться к разным конечным клеткам.
Проверка достижимости максимума. Один подходящий маршрут:
A1 → B1 → C1 → D1 → E1 → E2 → F2 → G2 → H2 → H3 → H4 → H5 → H6 → H7 → H8 → H9 → H10 → I10 → I11 → I12 → I13 → I14 → I15 → J15 → J16 → K16 → L16 → M16 → M17 → M18 → N18 → N19 → N20 → O20 → P20.
Сумма его монет: 8 + 16 + 58 + 55 + 98 + 95 + 90 + 89 + 86 + 72 + 62 + 80 + 54 + 72 + 67 + 73 + 41 + 81 + 59 + 64 + 85 + 87 + 80 + 76 + 57 + 99 + 82 + 85 + 84 + 72 + 98 + 79 + 95 + 71 + 6 = 2476.
Проверка достижимости минимума. Один подходящий маршрут:
A1 → A2 → A3 → A4 → A5 → A6 → A7 → A8 → B8 → C8 → D8 → E8 → F8.
Сумма его монет: 8 + 33 + 5 + 27 + 20 + 23 + 13 + 28 + 72 + 48 + 72 + 42 + 45 = 436.
В обоих маршрутах каждый следующий адрес отличается на один столбец вправо или на одну строку вниз, и ни один переход не пересекает толстую стену. Последние клетки закрыты справа и снизу, поэтому маршруты завершены по условию.
Рекурсия перебрала оба возможных последних хода в каждой из 400 клеток. Следовательно, большее максимальное или меньшее минимальное значение получить нельзя; приведённые маршруты достигают найденных границ.
Время и память для двух таблиц пропорциональны N². Порядок чисел в ответе: сначала максимум, затем минимум.
Ответ: 2476 436.