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