вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю пилоною. Квадрат ограничен внешними стенами. Между соседними клетками…

Задача: по таблице 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-таблицы (для максимума и минимума) и брать на выходе максимум и минимум по всем завершенным клеткам, как описано выше.