Задание 18: Робот-сборщик монет
Общая информация
- Тема: движение робота по сетке, сбор монет, поиск максимальной и минимальной суммы.
- Формат: робот движется командами «вправо» и «вниз» по полю N×N (или прямоугольному), на клетках лежат монеты. Могут быть внутренние стены.
- Ответ: два числа через пробел: сначала максимальная сумма, затем минимальная (среди всех допустимых путей из стартовой в конечную клетку).
Задания: N18.Робот | N18.Робот++
Идея решения
- Перебор всех допустимых путей или динамическое программирование: в каждой клетке храним максимальную (и минимальную) сумму, которую можно набрать, пройдя от этой клетки до финиша. Заполняем таблицу с правой нижней клетки, затем все остальные (так к моменту расчёта клетки уже готовы значения «вправо» и «вниз»).
- Старт: левая верхняя клетка. Финиш: правая нижняя (или указанная в условии).
- Получаются две таблицы: одна для максимума, одна для минимума. Число в левой верхней клетке в таблице макс. даёт максимальную сумму пути, в таблице мин. даёт минимальную сумму пути; вместе они и есть ответ.
Пример по шагам
Пример входных данных (поле 4×4, в клетках указаны монеты):
| 1 | 8 | 8 | 4 |
|---|---|---|---|
| 10 | 1 | 1 | 3 |
| 1 | 3 | 12 | 2 |
| 2 | 3 | 5 | 6 |
Робот может только вправо или вниз. Нужно найти максимальную и минимальную сумму монет по пути из (0,0) в (3,3).
Как заполняем. Заполняем с правой нижней клетки, затем все остальные (например, справа налево по строкам снизу вверх). В каждой клетке пишем: монета в этой клетке плюс лучший результат из соседей «вправо» и «вниз» (для макс берём максимум из двух, для мин берём минимум). На краях поля один из соседей отсутствует, берём только существующий.
| - | - | - | - |
|---|---|---|---|
| - | - | - | - |
| - | - | - | - |
| - | - | - | 6 |
| - | - | - | 15 |
|---|---|---|---|
| - | - | - | 11 |
| - | - | - | 8 |
| 16 | 14 | 11 | 6 |
Таблица макс (в клетке (i,j) стоит максимальная сумма пути от (i,j) до (3,3)):
| 41 | 40 | 32 | 15 |
|---|---|---|---|
| 37 | 26 | 24 | 11 |
| 27 | 26 | 23 | 8 |
| 16 | 14 | 11 | 6 |
Таблица мин (минимальная сумма пути от (i,j) до (3,3)):
| 22 | 21 | 20 | 15 |
|---|---|---|---|
| 23 | 13 | 12 | 11 |
| 17 | 17 | 20 | 8 |
| 16 | 14 | 11 | 6 |
Ответ: число в левой верхней клетке таблицы макс и число в левой верхней клетке таблицы мин: 41 и 22, то есть в бланке записываем 41 22.
Алгоритм по шагам реального задания
Задание: У робота команды вправо и вниз, найти МАКС и Допустим, у робота команды вправо и вниз суммы монет
- Скопировать таблицу, отметить ПРАВУЮ НИЖНЮЮ (начало) и ЛЕВУЮ ВЕРХНЮЮ (конец)
- Записать формулы в верхнюю (=AO20+T19) и левую (=AO20+S20) ячейку от ПРАВОЙ НИЖНЕЙ
- Затем выделяем всю таблицу и нажимаем Ctrl + H. В поле поиска вводим МАКС, в поле замены МИН и заменить все
- Готово! Теперь в синей ячейке МИН значение
- Ответ будет 2167 718