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