Максимальная и минимальная сумма
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Исполнитель Робот начинает движение из левой верхней клетки и может за одно перемещение перейти только в соседнюю клетку справа или вниз. Между соседними клетками могут находиться стены, через которые Робот пройти не может. Посетив клетку, Робот забирает монету, в том числе в начальной и конечной клетках маршрута. В клетке, которая справа и снизу ограничена стенами, движение заканчивается, а накопленная сумма считается итоговой. Определите максимальную и минимальную денежные суммы среди всех возможных маршрутов.
Для приведённого примера входных данных используется поле $4 \times 4$ без внутренних стен.
Условие как в банке ФИПИ — открыть и сверить
| ||||||||||||||||||||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Для каждой клетки определите лучшую и худшую сумму, с которой Робот может в неё попасть.
2Наводящая — какие числа считатьуровень 2 из 3
В клетку без стены Робот приходит сверху или слева. Максимум и минимум рассчитываются отдельно: к соответствующему значению добавляется монета текущей клетки.
3Прямая — фактически решениеуровень 3 из 3
Для примера максимальные суммы в последней строке равны $14$, $26$, $38$, $44$, а минимальные — $14$, $16$, $21$, $27$.