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