Робот и монеты

Что проверяет номер

Идея простая: в каждую клетку можно прийти только слева или сверху. Значит, лучшая сумма в клетке равна её монете плюс лучшее из двух соседних значений. Посчитав так всю таблицу по порядку, получаем ответ в конечной клетке, и перебирать пути не нужно.

Таблица 20×20 с монетами. Робот ходит вправо или вниз, стены нарисованы толстыми границами ячеек. Надо найти наибольшую и наименьшую сумму монет по пути в конечную клетку (из неё ходить некуда).

Шесть шагов

Посмотрим на маленьком поле 3×3. Клетка в первой строке получает сумму только слева, в первом столбце только сверху, а остальные выбирают большее из двух соседей. Для минимума то же самое, только выбирается меньшее.

1. Сделай копию таблицы. Копию кладём ниже или правее, на том же листе. Это будет таблица с формулами.
2. Делаем левую и верхнюю стенку. Первая строка и первый столбец: в них в клетку можно прийти только с одной стороны. Первая клетка — просто её монета. Дальше по первой строке =монета + слева, по первому столбцу =монета + сверху.
3. Заполняем всё остальное через МАКС. В каждой клетке: =монета + МАКС(слева; сверху). «Монета» — клетка из исходной таблицы, «слева» и «сверху» — клетки твоей таблицы с формулами. Формулу потом можно копировать протягиванием.
4. Вставляем таблицу, только формат. Копируем исходную таблицу, на таблицу с формулами вставляем «Специальная вставка» (Ctrl+Shift+V в LibreOffice, Ctrl+Alt+V в Excel) и выбираем «Только форматы». Так стены (границы) переезжают на таблицу с формулами.
5. Обрабатываем проблемные места и выделяем их. Проблемные места — клетки, у которых стена закрывает один из путей. Там формула другая: вместо МАКС(слева; сверху) берём только ту клетку, откуда можно прийти (=монета + слева или =монета + сверху). Если в клетку вообще нельзя попасть, формулу стираем (иначе она испортит соседей). Красим эти клетки, чтобы не потерять.
6. Чтобы найти минимум: Ctrl+H, заменяем МАКС на МИН. Проблемные клетки не трогаем, они и так с одним источником.

Ответ читаем в конечных клетках: клетках, из которых нельзя идти ни вправо, ни вниз. Наибольшее из них (при МАКС) и наименьшее (при МИН) — два числа ответа. Конечные клетки, в которые нельзя попасть, пропускаем.

Формулы с адресами ячеек

Пусть поле 3×3 лежит в ячейках A1:C3, а копию с формулами делаем в E1:G3. Каждая клетка копии считается из клетки поля и соседних клеток копии:

Формулу из F1 протяни вправо, из E2 вниз, а из F2 на всё оставшееся поле. Адреса сдвигаются сами, поэтому писать каждую клетку вручную не нужно.

Как учесть стену. Пусть стена стоит между F2 и G2. Тогда в G2 прийти можно только сверху, и формула становится =C2+G1. Если стена закрывает клетку и сверху, и слева, в неё попасть нельзя: сотри формулу. Такие клетки выдели цветом: при замене МАКС на МИН они не изменятся, и ты их не потеряешь.

Как заполняется таблица

Вот то же поле 3×3 после формул с МАКС и с МИН. Первая таблица с МАКС, вторая с МИН. В первой строке и первом столбце выбирать не из чего, поэтому там они совпадают.

Проверь центральную клетку сам: её значение равно монете 8 плюс лучшее из клеток слева и сверху. Так же считается каждая клетка поля.

Как смотреть, где стена

Стена просто убирает один из двух вариантов. В формуле такой клетки остаётся единственный источник.

Стена между двумя клетками — это толстая линия на границе: справа от левой клетки или слева от правой (рисуют по-разному). Проверяй обе стороны. На картинке стена видна глазами, ничего считать не надо.

Если ходы вправо и вверх, старт слева снизу, и «сверху» в формуле заменяется на «снизу». Смотри и на порядок ответа: иногда просят сначала наименьшую, потом наибольшую.

Ловушки