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

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

Наибольшая из итоговых сумм равна 2320, наименьшая — 860. Они могут относиться к разным конечным клеткам.
Проверка достижимости максимума. Один подходящий маршрут:
A1 → A2 → A3 → A4 → B4 → B5 → B6 → B7 → B8 → B9 → B10 → C10 → D10 → D11 → D12 → D13 → D14 → E14 → F14 → G14 → G15 → G16 → G17 → H17 → I17 → I18 → J18 → K18 → L18 → M18 → N18 → O18 → P18 → Q18 → Q19 → Q20.
Сумма его монет: 51 + 11 + 91 + 95 + 89 + 81 + 75 + 87 + 89 + 85 + 96 + 95 + 88 + 98 + 48 + 29 + 57 + 45 + 48 + 42 + 40 + 55 + 43 + 52 + 37 + 74 + 86 + 87 + 78 + 86 + 93 + 90 + 21 + 31 + 33 + 14 = 2320.
Проверка достижимости минимума. Один подходящий маршрут:
A1 → B1 → C1 → D1 → E1 → E2 → E3 → E4 → E5 → F5 → G5 → H5 → I5 → I6 → I7 → I8 → I9 → I10 → I11 → I12 → I13 → J13 → J14 → K14.
Сумма его монет: 51 + 9 + 89 + 74 + 36 + 38 + 31 + 26 + 8 + 8 + 16 + 18 + 39 + 98 + 87 + 10 + 15 + 13 + 52 + 20 + 22 + 24 + 34 + 42 = 860.
В обоих маршрутах каждый следующий адрес отличается на один столбец вправо или на одну строку вниз, и ни один переход не пересекает толстую стену. Последние клетки закрыты справа и снизу, поэтому маршруты завершены по условию.
Рекурсия перебрала оба возможных последних хода в каждой из 400 клеток. Следовательно, большее максимальное или меньшее минимальное значение получить нельзя; приведённые маршруты достигают найденных границ.
Время и память для двух таблиц пропорциональны N². Порядок чисел в ответе: сначала максимум, затем минимум.
Ответ: 2320 860.