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

Исходная таблица занимает диапазон $A1:T20$, поэтому $N=20$.
Внутренние вертикальные стены расположены справа от $B3:B6$, $I3$, $M4:M10$, $K8:K14$, $S8:S14$, $C14:C17$, $Q17:Q20$.
Горизонтальные стены расположены снизу от $F2:I2$, $N3:Q3$, $C6:G6$, $H14:K14$, $Q14:S14$, $M16:Q16$, $D17:H17$.
Расчётную таблицу разместим справа от исходной, начиная с ячейки $V1$.
В ячейку $V1$ запишем: $=A1$
В ячейку $W1$: $=V1+B1$ и скопируем вправо до $AO1$.
В ячейку $V2$: $=V1+A2$ и скопируем вниз до $V20$.
Для поиска максимальной суммы в $W2$ запишем: $=B2+МАКС(W1;V2)$ и скопируем формулу в диапазон $W2:AO20$.
Для первых клеток:
$V1=76$,
$W1=76+86=162$,
$V2=76+86=162$,
$W2=75+\max(162;162)=237$.
В клетках сразу справа от вертикальной стены можно попасть только сверху. Например, для $C3:C6$ в расчётной таблице используем диапазон $X3:X6$: $=C3+X2$ с копированием вниз.
Аналогично учитываем стены для диапазонов $AE3$, $AI4:AI10$, $AG8:AG14$, $AO8:AO14$, $Y14:Y17$, $AM17:AM20$.
В клетках сразу под горизонтальной стеной можно попасть только слева. Например, для $F3:I3$ используем диапазон $AA3:AD3$: $=F3+Z3$ с копированием вправо.
Аналогично обрабатываем диапазоны $AI4:AL4$, $X7:AB7$, $AC15:AF15$, $AL15:AN15$, $AH17:AL17$, $Y18:AC18$.
Клетка $N4$ закрыта стенами сверху и слева, поэтому попасть в неё нельзя. Из-за этого диапазон $N4:Q10$ также недостижим.
Конечными клетками являются $K14$, $S14$, $Q20$ и $T20$. Им соответствуют расчётные ячейки $AF14$, $AN14$, $AL20$, $AO20$.
Максимальные суммы в них:
$AF14=1774$,
$AN14=2138$,
$AL20=2598$,
$AO20=2553$.
Следовательно, $\max(1774;2138;2598;2553)=2598$.
Для поиска минимальной суммы в обычных клетках заменяем МАКС на МИН: $=B2+МИН(W1;V2)$
Формулы около стен остаются теми же.
Минимальные суммы в конечных клетках:
$AF14=762$,
$AN14=971$,
$AL20=1314$,
$AO20=1130$.
Следовательно, $\min(762;971;1314;1130)=762$.
Код на Python
Если сохранить исходную таблицу в формате CSV с именем 18-17.csv, результат можно проверить программой:
s = tuple(
tuple(map(int, row.split(';')))
for row in open('18-17.csv').read().splitlines()
)
N = len(s)
right = set()
for r1, r2, c in [
(3, 6, 2), (3, 3, 9), (4, 10, 13),
(8, 14, 11), (8, 14, 19),
(14, 17, 3), (17, 20, 17)
]:
for r in range(r1 - 1, r2):
right.add((r, c - 1))
down = set()
for r, c1, c2 in [
(2, 6, 9), (3, 14, 17), (6, 3, 7),
(14, 8, 11), (14, 17, 19),
(16, 13, 17), (17, 4, 8)
]:
for c in range(c1 - 1, c2):
down.add((r - 1, c))
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]
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 - 1) not in right:
if mn[i][j - 1] < 10 ** 9:
a.append(mn[i][j - 1])
b.append(mx[i][j - 1])
if i > 0 and (i - 1, j) not in down:
if mn[i - 1][j] < 10 ** 9:
a.append(mn[i - 1][j])
b.append(mx[i - 1][j])
if a:
mn[i][j] = s[i][j] + min(a)
mx[i][j] = s[i][j] + max(b)
ends = []
for i in range(N):
for j in range(N):
wall_right = j == N - 1 or (i, j) in right
wall_down = i == N - 1 or (i, j) in down
if wall_right and wall_down and mn[i][j] < 10 ** 9:
ends.append((mn[i][j], mx[i][j]))
print(max(x[1] for x in ends), min(x[0] for x in ends))
Программа выводит:
$2598$ $762$