Задание №18. Робот в таблице: минимальная и максимальная сумма

Робот движется по прямоугольной таблице, переходя на одну клетку вправо или вниз. Каждая посещённая клетка добавляет своё число к сумме: это могут быть собранные монеты или плата за посещение. Требуется найти наименьший и наибольший результат допустимого маршрута. Вместо перебора всех маршрутов достаточно для каждой клетки вычислить две суммы от старта до неё.

Что означает сумма в клетке

Число исходной таблицы относится только к одной клетке. Накопленная сумма относится ко всему пути от старта до этой клетки включительно. Если в клетку можно прийти несколькими путями, отдельно сохраняются минимальная и максимальная накопленные суммы.

При движении вправо и вниз последний шаг в клетку возможен только слева или сверху. Такие предыдущие клетки называются предшественниками. Поэтому минимальная сумма получается из меньшей накопленной суммы доступных предшественников, а максимальная — из большей. После выбора прибавляется собственное число текущей клетки. Сравниваются результаты путей, а не два соседних числа исходной таблицы.

Полный пример: поле без внутренних стен

В задаче о плате за посещение клетки ↗ файл 613_18.xlsx содержит поле 15×15. Старт находится в A1, финиш — в O15; разрешены только шаги вправо и вниз, внутренних стен нет. Оплачиваются все посещённые клетки, включая начало и конец. В ответе требуется сначала минимум, затем максимум.

Начальная клетка и края

Ниже приведён настоящий левый верхний фрагмент A1:C3 большой таблицы. Он нужен для объяснения первых вычислений и не заменяет остальные клетки файла.

В A1 Робот уже находится, поэтому обе начальные суммы равны 22. Чтобы попасть в B1, нужен единственный шаг из A1: 22+21=43. Чтобы попасть в A2, нужен шаг из A1 вниз: 22+28=50. В первой строке нельзя прийти сверху, а в первом столбце — слева. Поэтому вдоль каждого края минимум и максимум совпадают: маршрут пока единственный.

Продолжая вправо, в C1 получается 22+21+12=55. Продолжая вниз, в A3 получается 22+28+29=79. Эти значения понадобятся для соседних внутренних клеток.

Первый выбор между путями

В B2 записано 11. Последняя клетка перед ней — B1 или A2; накопленные суммы в них равны 43 и 50. Поэтому для минимума выбирается 43 и прибавляется 11, а для максимума выбирается 50 и тоже прибавляется 11. Выбор меньшего числа обозначается \min, большего — \max:

11+\min(43,50)=54,
11+\max(43,50)=61.

Полученные 54 и 61 уже включают значение B2. При следующем шаге его повторно прибавлять не нужно.

Для B3 предшественниками служат B2 и A3. Минимальная сумма равна 12+\min(54,79)=66, максимальная — 12+\max(61,79)=91. В первой формуле участвует минимум из B2, во второй — максимум из B2: эти два расчёта ведутся независимо.

Для C2 получаются 17+\min(55,54)=71 и 17+\max(55,61)=78. Теперь известны обе клетки перед C3: сверху C2, слева B3. Поэтому в C3 минимум равен 18+\min(71,66)=84, а максимум — 18+\max(78,91)=109.

В каждой ячейке следующей таблицы сначала стоит минимальная, затем максимальная накопленная сумма. Это результаты только для клеток фрагмента.

Для этих девяти клеток других предшественников нет. Путь не может сначала выйти вправо или вниз за фрагмент, а потом вернуться: обратные шаги запрещены. Поэтому вычисления фрагмента верны и внутри большого поля.

Продолжение в электронной таблице

Исходное поле остаётся на отдельном листе с именем Данные. На двух пустых листах Минимум и Максимум строятся таблицы тех же размеров, A1:O15. Адрес клетки на каждом листе соответствует одной и той же клетке поля. Ниже используются формулы русской версии Excel; знак ! отделяет имя листа от адреса.

На листе Минимум в A1 записывается =Данные!A1. Формула =Данные!B1+A1 в B1 складывает число исходной B1 с накопленной суммой слева. Она копируется по первой строке до O1. В A2 формула =Данные!A2+A1 добавляет значение исходной A2 к сумме сверху; она копируется вниз до A15.

Когда края заполнены, в B2 записывается формула:

=Данные!B2+МИН(B1;A2)

Ссылки B1 и A2 относятся к листу Минимум, поэтому в них уже находятся суммы путей. Формула копируется по внутренней области B2:O15. При сдвиге в C2 ссылки сами становятся C1 и B2, а ссылка на исходное число — Данные!C2. Такие ссылки называются относительными.

На листе Максимум начальная клетка и края заполняются теми же формулами. Во внутренней области используется =Данные!B2+МАКС(B1;A2), скопированная из B2. Здесь соседние суммы уже берутся с листа Максимум. Смешивание ссылок на два расчётных листа нарушило бы смысл вычисления.

Ответ для полного поля

Расчёт продолжается по всем 225 клеткам. Перед финишем минимальные суммы в O14 и N15 равны 436 и 426, максимальные — 654 и 657. В самой O15 стоит 12, поэтому последний шаг расчёта даёт:

12+\min(436,426)=438,
12+\max(654,657)=669.

Значение O15 на листе Минимум равно 438, а на листе Максимум — 669. Значения 84 и 109 из C3 не были ответом: от C3 до O15 остаётся продолжение пути, и другие маршруты к O15 могут вообще не проходить через C3.

Ответ: 438 669. Его порядок соответствует условию. Любой путь из A1 в O15 содержит 14 шагов вправо и 14 вниз, то есть 14+14+1=29 посещённых клеток. Единица учитывает начальную клетку до первого шага.

Для проверки найденной суммы можно восстановить путь назад: от O15 переходить к тому предшественнику, чья накопленная сумма была выбрана формулой. Для минимума используется лист Минимум, для максимума — лист Максимум. Если суммы равны, подходит любой из двух предшественников. Сумма 29 исходных чисел вдоль восстановленного пути должна совпасть с результатом в O15.

Стены и недостижимые клетки

Стена запрещает определённый переход между соседними клетками. Она не удаляет обе клетки и не меняет записанные в них числа. В задаче с внутренними стенами и финишем T20 ↗ это меняет набор предшественников для отдельных клеток.

Например, если сверху от некоторой клетки проходит стена, прийти сверху нельзя. При доступном пути слева её сумма получается только из левого предшественника и собственного числа. Если стена только слева, остаётся верхний предшественник. Если ни от одного разрешённого соседа нет пути от старта, клетка недостижима: накопленной суммы в ней нет.

Поэтому формула с двумя соседями не копируется через стены без изменения. Для клетки с единственным доступным предшественником оставляется только его сумма. Недостижимая клетка отмечается отдельно и не участвует в дальнейших сравнениях. Пустая ячейка или ноль сами по себе не обеспечивают этого: формула может принять их за значение и создать несуществующий путь.

Когда маршрут заканчивается в тупике

Финиш не всегда задан правым нижним углом. В задаче о движении до любой конечной клетки ↗ Робот движется, пока существует разрешённый шаг вправо или вниз. Тупик здесь — клетка, из которой оба таких выхода закрыты стеной или внешней границей поля.

В рабочем поле достижимы четыре тупика. Расчёт накопленных сумм для них даёт:

Минимум выбирается среди четырёх минимальных сумм и равен 436. Максимум выбирается среди четырёх максимальных сумм и равен 2476. Они относятся к разным конечным клеткам, что допустимо: это два разных маршрута. Условие этой задачи требует максимум первым, поэтому ответ записывается как 2476 436.

Возможные ловушки

• Выбор меньшего соседнего числа. В примере без стен ↗ в клетку E2 со значением 10 можно прийти сверху из E1, где стоит 25, или слева из D2, где стоит 29. Меньше исходное число сверху, но минимальные накопленные суммы равны 109 сверху и 100 слева. Верный результат — 10+100=110. Выбор по исходным числам дал бы 119. Поэтому ссылки на соседей ведут в расчётную таблицу.
• Ноль за стеной. В поле с внутренними стенами ↗ обнуление недоступного перехода может сделать его ложным победителем при поиске минимума. Из сравнения удаляется запрещённый предшественник, а другой путь в ту же клетку сохраняется, если он существует.
• Только правый нижний угол. В задаче с несколькими тупиками ↗ это потеряет и минимум в F8, и максимум в P20. Сначала по стенам и границам определяются все допустимые конечные клетки, затем сравниваются результаты для достижимых.
• Пропуск старта или исправление числа по догадке. В задаче с оговоркой о начальной клетке ↗ фактическое значение A1 равно 102; несоответствие исходному диапазону пояснено в условии. Замена на 100 уменьшит каждую сумму на 2, а замена на ноль — на 102. В расчёт берётся число файла и учитывается с самого старта.
• Маленькая иллюстрация вместо рабочего файла. В задаче с отдельным рисунком-примером ↗ настоящее поле имеет размер 15×15. Ответ для иллюстрации не является ответом для файла. Размеры, числа и стены проверяются именно в рабочей таблице.