Вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю пилоною. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. В «угловых» клетках поля - тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых суми, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные' представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями. Пример входных данных 1 8 8 4 10 1 1 3 1 3 12 2 2 3 5 6

Задача: по таблице N×N с числами ( coin в каждой клетке) найти максимальную и минимальную итоговую сумму монет, которую может собрать робот, если он стартует в левой верхней клетке и может идти только вправо или вниз, пока не окажется в «конечной» клетке (у которой из-за стен нельзя продолжать движение). В примере входа данная таблица 4×4 без указания внутренних стен, значит вычисляем для обычного случая без дополнительных блокировок между клетками. Данные примера (N=4): - Ряд 1: 1 8 8 4 - Ряд 2: 10 1 1 3 - Ряд 3: 1 3 12 2 - Ряд 4: 2 3 5 6 Пояснение к подходу - Если у нас нет внутренних стен между соседними клетками, роботу доступны переходы вправо и вниз во всех клетках, кроме граничных, и единственная выходная «конечная» клетка — последняя клетка внизу справа (4,4). В этом случае задача сводится к нахождению максимальной и минимальной сумм по всем путям из (1,1) в (4,4). - Общий подход: динамическое программирование. - Для каждой клетки (i,j) вычисляем: - maxSum[i][j] = значение в клетке (i,j) + max(maxSum[i-1][j], maxSum[i][j-1]) (при отсутствии соседей сверху или слева используем только существующий источник). - minSum[i][j] = значение в клетке (i,j) + min(minSum[i-1][j], minSum[i][j-1]) - Итоговую максимальную сумму можно получить как max по всем «конечным» клеткам, а минимальную — как min по всем «конечным» клеткам. В случае отсутствия внутренних стен концами является только (N,N). Решение для данного примера 1) Примем, что нет внутренних стен, ни одна клетка не ограничена кроме границ. 2) Вычислим таблицы maxSum и minSum. maxSum (макс сумма до каждой клетки): - Row 1: 1, 9, 17, 21 - Row 2: 11, 12, 18, 24 - Row 3: 12, 15, 30, 32 - Row 4: 14, 18, 35, 41 minSum (мин сумма до каждой клетки): - Row 1: 1, 9, 17, 21 - Row 2: 11, 10, 11, 14 - Row 3: 12, 13, 23, 16 - Row 4: 14, 16, 21, 22 3) Конечные клетки: в отсутствии внутренних стен это одна клетка (4,4). Поэтому: - Максимальная итоговая сумма = maxSum[4][4] = 41 - Минимальная итоговая сумма = minSum[4][4] = 22 Проверочные маршруты - Максимальная сумма 41 достигается, например, по пути: (1,1) -> (1,2) -> (1,3) -> (2,3) -> (3,3) -> (4,3) -> (4,4) Сумма: 1 + 8 + 8 + 1 + 12 + 5 + 6 = 41. - Минимальная сумма 22 достигается по пути: (1,1) -> (1,2) -> (2,2) -> (2,3) -> (2,4) -> (3,4) -> (4,4) Сумма: 1 + 8 + 1 + 1 + 3 + 2 + 6 = 22. Ответ - Максимальная сумма: 41 - Минимальная сумма: 22 Итог: 41 22 Замечание - Если в задаче будут задана карта внутренних стен между клетками, алгоритм не изменится принципиально: вместо прямых переходов вправо/вниз учитываются только разрешённые переходы (если между клетками есть стена — переход невозможен). Тогда можно вычислять аналогично две DP-таблицы (для максимума и минимума) и брать на выходе максимум и минимум по всем завершенным клеткам, как описано выше.