Максимальный и минимальный путь
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Робот начинает движение из левой верхней клетки и за один шаг может переместиться только вправо или вниз. Сквозь внутренние и внешние стены Робот пройти не может. Посетив клетку, Робот забирает монету. В клетке, которая справа и снизу ограничена стенами, движение заканчивается, а накопленная сумма считается итоговой. Определите максимальную и минимальную денежные суммы среди всех возможных маршрутов.
Исходные данные представлены в прилагаемом файле электронной таблицы. Для приведённого примера без внутренних стен таблица имеет вид: $\begin{matrix}1&8&8&4\\10&1&1&3\\1&3&12&2\\2&3&5&6\end{matrix}$.
Условие как в банке ФИПИ — открыть и сверить
| ||||||||||||||||||||||
| | ||||||||||||||||||||||
Формат: өлшем бірліктері жоқ сан немесе сөз; бөлшек бөлігін үтірмен бөліңіз.
1Мягкая — с чего смотретьдеңгей 1 из 3
Для каждой клетки определите лучшую и худшую сумму, с которой Робот может в неё попасть.
2Жетекші — қандай сандарды есептеудеңгей 2 из 3
В клетку можно прийти только сверху или слева, поэтому используйте максимум или минимум из этих двух значений и прибавьте монету текущей клетки.
3Тікелей — іс жүзінде шешімдеңгей 3 из 3
Для приведённой таблицы максимальная сумма равна $38$, а минимальная — $21$. Жауабы: $3821$.