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=18$,
$R1=18+23=41$,
$Q2=18+13=31$,
$R2=27+\max(41;31)=68$.
В ячейке AE15 получим максимальную сумму: $707$.
Для поиска минимальной суммы в R2 запишем: =ЕСЛИ(Q2<R1;Q2+B2;R1+B2)
Скопируем формулу в диапазон R2:AE15.
Для первых клеток: $R2=27+\min(41;31)=58$.
В ячейке AE15 получим минимальную сумму: $486$.
Код на Python
Если сохранить исходную таблицу в формате CSV с именем 18-09.csv:
s = tuple(
tuple(map(int, row.split(';')))
for row in open('18-09.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] = mn[0][j - 1] + s[0][j]
mx[0][j] = mx[0][j - 1] + s[0][j]
for i in range(1, N):
mn[i][0] = mn[i - 1][0] + s[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])
Программа выводит:
486 707