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