18. Исполнитель Робот: Между соседними клетками могут быть внутренние стены, сквозь которые Робот…
Квадрат разлинован на $N\times N$ клеток, где $1<N<30$. Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Между соседними клетками могут быть внутренние стены, сквозь которые Робот пройти не может.
Перед каждым запуском Робота в каждой клетке лежит монета достоинством от $1$ до $100$. Посетив клетку, Робот забирает монету с собой, включая начальную и конечную клетки.
Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите сначала максимальную сумму, затем минимальную.
Пример входных данных:

Исходная таблица занимает диапазон $A1:T20$, поэтому $N=20$.
В файле имеются внутренние стены справа от клеток $F4:F15$ и снизу от клеток $L17:Q17$.
Расчётную таблицу разместим справа от исходной, начиная с ячейки $V1$.
В ячейку $V1$ запишем: $=A1$
В ячейку $W1$: $=V1+B1$
Скопируем формулу вправо до $AO1$.
В ячейку $V2$ запишем: $=V1+A2$
Скопируем формулу вниз до $V20$.
Для поиска максимальной суммы в ячейку $W2$ запишем: $=B2+МАКС(W1;V2)$
Скопируем формулу в диапазон $W2:AO20$.
Для первых клеток:
$V1=102$,
$W1=102+27=129$,
$V2=102+19=121$,
$W2=66+\max(129;121)=195$.
Из-за стены справа от $F4:F15$ в клетки $G4:G15$ можно попасть только сверху. В расчётной таблице это диапазон $AB4:AB15$.
В ячейку $AB4$ запишем: $=G4+AB3$ и скопируем до $AB15$.
Через стену под клетками $L17:Q17$ нельзя пройти вниз, поэтому в клетки $L18:Q18$ можно попасть только слева.
В ячейку $AG18$ запишем: $=L18+AF18$ и скопируем вправо до $AL18$.
В ячейке $AO20$ получим максимальную сумму: $2337$.
Для поиска минимальной суммы в ячейке $W2$ используем: $=B2+МИН(W1;V2)$ и скопируем формулу в диапазон $W2:AO20$.
Затем снова зададим специальные формулы для клеток около стен: $AB4=G4+AB3$ с копированием до $AB15$, $AG18=L18+AF18$ с копированием до $AL18$.
Для первых клеток: $W2=66+\min(129;121)=187$.
В ячейке $AO20$ получим минимальную сумму: $1275$.
Ответ: $2337$ $1275$.
Код на Python
Если сохранить таблицу в формате CSV с именем 18-15.csv, решение на Python будет выглядеть так:
s = tuple(
tuple(map(int, row.split(';')))
for row in open('18-15.csv').read().splitlines()
)
N = len(s)
mn = [[10 ** 9] * N for _ in range(N)]
mx = [[-10 ** 9] * N for _ in range(N)]
mn[0][0] = mx[0][0] = s[0][0]
# Нельзя войти слева в G4:G15
wall_left = {(i, 6) for i in range(3, 15)}
# Нельзя войти сверху в L18:Q18
wall_top = {(17, j) for j in range(11, 17)}
for i in range(N):
for j in range(N):
if i == 0 and j == 0:
continue
a = []
b = []
if j > 0 and (i, j) not in wall_left:
a.append(mn[i][j - 1])
b.append(mx[i][j - 1])
if i > 0 and (i, j) not in wall_top:
a.append(mn[i - 1][j])
b.append(mx[i - 1][j])
mn[i][j] = s[i][j] + min(a)
mx[i][j] = s[i][j] + max(b)
print(mx[-1][-1], mn[-1][-1])
Программа выводит:
$2337$ $1275$