Шешімі: Минимальный и максимальный путь
Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз — в соседнюю нижнюю. Робот разрушается при попытке выхода за границу квадрата или при попытке пересечения стены клетки. В таблице стены отмечены границами с утолщением.
Перед запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке — это натуральное число, не превышающее 100. Это правило относится к начальной и конечной клеткам маршрута Робота.
Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку.
Исходные данные представлены в форме электронной таблицы размером $N \times N$, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.
Шешімін қадамдап көрсету
5 қадамОбозначим через $m_{i,j}$ минимальную, а через $M_{i,j}$ максимальную сумму бонусов на пути из левой верхней клетки в клетку $(i,j)$.
Начальные значения для левой верхней клетки равны её бонусу: она кіреді в сумму маршрута.
$$m_{1,1}=M_{1,1}=b_{1,1}$$Для каждой следующей клетки рассмотрим возможные переходы из клетки сверху и из клетки слева. Переход через стену исключается.
Минимальная сумма получается добавлением бонуса клетки к минимальной из доступных сумм, максимальная — к максимальной из доступных сумм.
$$m_{i,j}=b_{i,j}+\min\limits_{(p,q)\to(i,j)}m_{p,q},\quad M_{i,j}=b_{i,j}+\max\limits_{(p,q)\to(i,j)}M_{p,q}$$В правой нижней клетке получаются искомые минимальная и максимальная суммы. Их записывают в указанном порядке.
Числа зависят от содержимого электронной таблицы, которое не представлено в исходных данных.
Бұл жауап талдау нәтижесінде алынды, бірақ банктің ресми кілтімен тексерілген жоқ — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Не учитывать бонус начальной или конечной клетки.
Разрешать переход через стену.
Использовать только один из двух нұсқа пути и не сравнивать все допустимые маршруты.
Перепутать порядок жазбалар минимальной и максимальной сумм.