Решение: Максимальная и минимальная сумма
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Робот начинает движение из левой верхней клетки и может перемещаться только вправо или вниз, если между соседними клетками нет стены. Посетив клетку, робот забирает монету, в том числе в начальной и конечной клетках маршрута. В клетках, которые справа и снизу ограничены стенами, робот прекращает движение; накопленная сумма считается итоговой. Определите максимальную и минимальную суммы среди всех возможных маршрутов. Исходные данные находятся в прилагаемом файле: электронная таблица содержит значения монет, а утолщённые линии обозначают внутренние и внешние стены.
Решение по шагам
4 шагаОбрабатываем клетки электронной таблицы слева направо и сверху вниз. В каждой клетке учитываем только те переходы сверху или слева, которые не пересекают стену.
Для каждой достижимой клетки сохраняем две величины: максимальную и минимальную сумму монет на пути из начальной клетки.
$$\mathrm{maxSum}_{i,j}=a_{i,j}+\max(\mathrm{maxSum}_{i-1,j},\mathrm{maxSum}_{i,j-1})$$Минимальная сумма рассчитывается аналогично с помощью минимума.
$$\mathrm{minSum}_{i,j}=a_{i,j}+\min(\mathrm{minSum}_{i-1,j},\mathrm{minSum}_{i,j-1})$$После заполнения таблиц рассматриваем все клетки, у которых справа и снизу стоят стены. Максимальный ответ — наибольшее значение максимальной суммы в этих клетках, минимальный ответ — наименьшее значение минимальной суммы.
Максимальная и минимальная суммы определяются по приложенной электронной таблице.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Учитывают только правую нижнюю клетку, хотя конечных клеток может быть несколько.
Не добавляют стоимость начальной или конечной клетки.
Переходят через внутреннюю стену.
Ищут один и тот же путь для максимальной и минимальной суммы.