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

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

Наибольшая из итоговых сумм равна 2468, наименьшая — 969. Они могут относиться к разным конечным клеткам.
Проверка достижимости максимума. Один подходящий маршрут:
A1 → A2 → A3 → B3 → B4 → B5 → B6 → B7 → C7 → C8 → D8 → D9 → D10 → E10 → F10 → G10 → G11 → G12 → G13 → G14 → G15 → H15 → I15 → I16 → I17 → I18 → J18 → K18 → L18 → M18 → N18 → O18 → P18 → Q18 → Q19 → Q20.
Сумма его монет: 99 + 83 + 93 + 98 + 94 + 92 + 85 + 80 + 82 + 92 + 89 + 98 + 99 + 85 + 78 + 78 + 28 + 55 + 42 + 55 + 29 + 33 + 43 + 54 + 21 + 99 + 88 + 96 + 77 + 71 + 80 + 99 + 19 + 31 + 7 + 16 = 2468.
Проверка достижимости минимума. Один подходящий маршрут:
A1 → B1 → C1 → D1 → E1 → E2 → F2 → G2 → H2 → I2 → J2 → K2 → K3 → K4 → K5 → K6 → K7 → K8 → K9 → K10 → K11 → K12 → K13 → K14.
Сумма его монет: 99 + 72 + 70 + 90 + 38 + 46 + 28 + 23 + 33 + 14 + 25 + 8 + 7 + 17 + 46 + 87 + 91 + 26 + 17 + 12 + 21 + 32 + 24 + 43 = 969.
В обоих маршрутах каждый следующий адрес отличается на один столбец вправо или на одну строку вниз, и ни один переход не пересекает толстую стену. Последние клетки закрыты справа и снизу, поэтому маршруты завершены по условию.
Рекурсия перебрала оба возможных последних хода в каждой из 400 клеток. Следовательно, большее максимальное или меньшее минимальное значение получить нельзя; приведённые маршруты достигают найденных границ.
Время и память для двух таблиц пропорциональны N². Порядок чисел в ответе: сначала максимум, затем минимум.
Ответ: 2468 969.