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