18. Исполнитель Робот: Квадрат разлинован на N× N клеток (1<N<26)
Квадрат разлинован на $N\times N$ клеток $(1<N<26)$. Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Робот разрушается при попытке выхода за границу квадрата или при попытке пересечения стены клетки. В таблице стены отмечены границами с утолщением.
Перед запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке – это натуральное число, не превышающее $100$. Это правило относится к начальной и конечной клеткам маршрута Робота.
Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. В ответе укажите два числа: сначала минимальную сумму, затем максимальную.
Исходные данные представлены в форме электронной таблицы размером $N\times N$, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.
Пример входных данных:

Для указанных входных данных ответом является пара чисел: $27$ $41$.
В исходном файле таблица занимает диапазон A1:O15, поэтому размер квадрата равен $N=15$.
Внутренних стен в таблице нет. В каждую клетку, кроме клеток верхней строки и левого столбца, Робот может попасть либо слева, либо сверху.
Расчётную таблицу разместим справа от исходной, начиная с ячейки Q1.
В ячейку Q1 запишем: =СУММ($A$1:A1)
Скопируем формулу в диапазоны R1:AE1 и Q2:Q15.
Для поиска максимальной суммы в ячейку R2 запишем: =ЕСЛИ(Q2>R1;Q2+B2;R1+B2) и скопируем в диапазон R2:AE15.
Для первых клеток получаем:
$Q1=22$,
$R1=22+29=51$,
$Q2=22+30=52$,
$R2=17+\max(51;52)=69$.
В ячейке AE15 получим максимальную сумму: $679$.
Для поиска минимальной суммы в R2 запишем: =ЕСЛИ(Q2<R1;Q2+B2;R1+B2) и также скопируем в диапазон R2:AE15.
Например: $R2=17+\min(51;52)=68$.
В ячейке AE15 получим минимальную сумму: $464$.
По условию сначала записывается минимальная сумма, затем максимальная.
Код на Python
Если сохранить исходную таблицу в формате CSV с именем 18-06.csv:
s = tuple(
tuple(map(int, row.split(';')))
for row in open('18-06.csv').read().splitlines()
)
N = len(s)
mn = [[0] * N for _ in range(N)]
mx = [[0] * N for _ in range(N)]
mn[0][0] = mx[0][0] = s[0][0]
for j in range(1, N):
mn[0][j] = mx[0][j] = mx[0][j - 1] + s[0][j]
for i in range(1, N):
mn[i][0] = mx[i][0] = mx[i - 1][0] + s[i][0]
for i in range(1, N):
for j in range(1, N):
mn[i][j] = s[i][j] + min(mn[i - 1][j], mn[i][j - 1])
mx[i][j] = s[i][j] + max(mx[i - 1][j], mx[i][j - 1])
print(mn[-1][-1], mx[-1][-1])
Программа выводит:
464 679