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