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