Решение: Минимальный и максимальный путь
Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Робот разрушается при попытке выхода за границу квадрата или при попытке пересечения стены клетки. В таблице стены отмечены границами с утолщением.
Перед запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке — натуральное число, не превышающее 100. Это правило относится к начальной и конечной клеткам маршрута Робота.
Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. Исходные данные представлены в форме электронной таблицы размером $N \times N$, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.
Решение по шагам
4 шагаСоздаём две таблицы динамического программирования: в первой храним минимальную, во второй — максимальную сумму бонусов для каждого достижимого маршрута от левой верхней клетки до текущей.
Для каждой клетки рассматриваем переход из верхней клетки и из левой клетки. Переход исключается, если между клетками есть стена.
К бонусу текущей клетки прибавляем минимум или максимум из допустимых значений предыдущих клеток. Для начальной клетки записываем её собственный бонус.
После обработки всей таблицы значения в правой нижней клетке являются искомыми минимальной и максимальной суммами.
Впишите найденные минимальную и максимальную суммы бонусов.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Не учитывают бонус начальной клетки.
Не учитывают бонус конечной клетки.
Разрешают переход через утолщённую границу.
Путают порядок вывода: сначала требуется минимум, затем максимум.
Используют только один оптимальный маршрут вместо отдельного поиска минимума и максимума.