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