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