18. Исполнитель Робот: все задания

В исходном файле таблица занимает диапазон A1:O15, поэтому размер квадрата равен $N=15$.

Внутренних стен в данной таблице нет, поэтому в каждую клетку, кроме клеток верхней строки и левого столбца, Робот может попасть либо из клетки слева, либо из клетки сверху.

Сначала найдём максимальную сумму бонусов. Для этого найдём максимальную сумму для каждой клетки таблицы.

Для каждой клетки верхней строки существует только один способ попасть в неё: двигаться всё время вправо. Поэтому значение для такой клетки равно сумме всех клеток слева от неё вместе с текущей клеткой.

Для каждой клетки левого столбца существует только один способ попасть в неё: двигаться всё время вниз. Поэтому значение равно сумме всех клеток выше неё вместе с текущей клеткой.

Расчётную таблицу разместим справа от исходной, начиная с ячейки Q1.

В ячейку Q1 запишем формулу: =СУММ($A$1:A1)

Скопируем эту формулу во все ячейки диапазона R1:AE1 и диапазона Q2:Q15.

Для остальных клеток будем сравнивать значение ячейки слева и значение ячейки сверху. Выбираем большее из них и прибавляем значение соответствующей клетки исходной таблицы.

В ячейку R2 запишем формулу: =ЕСЛИ(Q2>R1;Q2+B2;R1+B2)

Скопируем эту формулу во все ячейки диапазона R2:AE15. Например, для первых клеток получаем:

$Q1=27$,
$R1=27+13=40$,
$Q2=27+24=51$,
$R2=30+\max(40;51)=81$.

Таким образом, в ячейке AE15 получим значение максимальной суммы бонусов: $710$.

Аналогичным образом найдём минимальную сумму бонусов.

Ячейки диапазонов Q1:Q15 и R1:AE1 заполняются так же, как при поиске максимальной суммы.

Для остальных клеток теперь нужно выбирать меньшее из значений слева и сверху.

В ячейку R2 запишем формулу: =ЕСЛИ(Q2<R1;Q2+B2;R1+B2)

Скопируем эту формулу во все ячейки диапазона R2:AE15. Например, $R2=30+\min(40;51)=70$.

Таким образом, в ячейке AE15 получим значение минимальной суммы бонусов: $485$.

По условию сначала записывается минимальная сумма, затем максимальная: $485\ 710$.

Код на Python

Если сохранить исходную таблицу в формате CSV с именем 18-01.csv, решение можно записать так:

s = tuple(
    tuple(int(x) for x in row.split(';'))
    for row in open('18-01.csv').read().splitlines()
)

N = len(s)

ans = []

for f in [min, max]:
    m = [[0 for _ in range(N)] for _ in range(N)]

    m[0][0] = s[0][0]

    for i in range(1, N):
        m[0][i] = s[0][i] + m[0][i - 1]
        m[i][0] = s[i][0] + m[i - 1][0]

    for row in range(1, N):
        for column in range(1, N):
            m[row][column] = (
                s[row][column]
                + f(m[row - 1][column], m[row][column - 1])
            )

    ans.append(m[N - 1][N - 1])

print(*ans)

Программа выводит:

485 710

В исходном файле находится таблица размером $20\times20$.

Для каждой клетки будем вычислять две величины:

• $max[i][j]$ — максимальная сумма, с которой Робот может попасть в клетку;
• $min[i][j]$ — минимальная сумма.

Если в клетку можно попасть и сверху, и слева, то:

$max[i][j]=a[i][j]+\max(max[i-1][j],max[i][j-1])$
$min[i][j]=a[i][j]+\min(min[i-1][j],min[i][j-1])$

Если между клетками есть стена, соответствующий переход не рассматриваем.

В таблице получаются четыре конечные клетки:

Максимальная итоговая сумма: $\max(1974,2258,1854,2256)=2258$

Минимальная итоговая сумма: $\min(893,1056,975,1099)=893$

Ответ: $2258\ 893$.

Код на Python

Таблицу с числами сохраняем в формате CSV под именем 18-02.csv. Координаты стен задаём по исходной электронной таблице.

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-02.csv').read().splitlines()
)

N = len(s)

# Вертикальные стены.
# Тройка (r1, r2, c) означает стену справа от столбца c
# от строки r1 до строки r2.
vr = set()

for r1, r2, c in [
    (3, 12, 17),
    (4, 8, 2),
    (4, 7, 13),
    (10, 15, 12),
    (11, 14, 10),
    (11, 18, 19),
    (13, 18, 3),
    (17, 20, 15)
]:
    for r in range(r1, r2 + 1):
        vr.add((r - 1, c - 1))

# Горизонтальные стены.
# Тройка (r, c1, c2) означает стену снизу от строки r
# от столбца c1 до столбца c2.
hd = set()

for r, c1, c2 in [
    (3, 8, 13),
    (8, 3, 5),
    (9, 13, 14),
    (10, 6, 10),
    (12, 16, 17),
    (16, 10, 15),
    (18, 4, 6),
    (18, 17, 19)
]:
    for c in range(c1, c2 + 1):
        hd.add((r - 1, c - 1))

INF = 10 ** 9

mx = [[-INF] * N for _ in range(N)]
mn = [[INF] * N for _ in range(N)]

mx[0][0] = mn[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 i > 0 and (i - 1, j) not in hd and mx[i - 1][j] != -INF:
            a.append(mx[i - 1][j])
            b.append(mn[i - 1][j])

        # Приход слева
        if j > 0 and (i, j - 1) not in vr and mx[i][j - 1] != -INF:
            a.append(mx[i][j - 1])
            b.append(mn[i][j - 1])

        if a:
            mx[i][j] = s[i][j] + max(a)
            mn[i][j] = s[i][j] + min(b)

ans_max = []
ans_min = []

for i in range(N):
    for j in range(N):
        right_wall = j == N - 1 or (i, j) in vr
        down_wall = i == N - 1 or (i, j) in hd

        if right_wall and down_wall and mx[i][j] != -INF:
            ans_max.append(mx[i][j])
            ans_min.append(mn[i][j])

print(max(ans_max), min(ans_min))

Программа выводит:

2258 893

В исходном файле таблица занимает диапазон 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+44=62$,
$Q2=18+12=30$,
$R2=36+\max(62;30)=98$.

В ячейке AE15 получим максимальную сумму: $1043$.

Для поиска минимальной суммы заменим сравнение в R2:

=ЕСЛИ(Q2<R1;Q2+B2;R1+B2)

После копирования формулы в диапазон R2:AE15 получим: $645$.

Ответ: $645\ 1043$.

Код на Python

Сохраним исходную таблицу в формате CSV под именем 18-04.csv.

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-04.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])

Программа выводит:

645 1043

В исходном файле таблица занимает диапазон A1:O15, поэтому размер квадрата равен $N=15$.

Внутренних стен в таблице нет, поэтому в каждую клетку, кроме клеток верхней строки и левого столбца, Робот может попасть либо из клетки слева, либо из клетки сверху.

Расчётную таблицу разместим справа от исходной, начиная с ячейки Q1.

В ячейку Q1 запишем формулу: =СУММ($A$1:A1)

Скопируем её в диапазоны R1:AE1 и Q2:Q15.

Сначала найдём максимальную сумму. Для остальных клеток выбираем большее из значений слева и сверху.

В ячейку R2 запишем: =ЕСЛИ(Q2>R1;Q2+B2;R1+B2)

Скопируем формулу в диапазон R2:AE15.

Например:

$Q1=21$,
$R1=21+12=33$,
$Q2=21+18=39$,
$R2=10+\max(33;39)=49$.

В ячейке AE15 получим максимальную сумму бонусов: $698$.

Аналогично найдём минимальную сумму. Для остальных клеток выбираем меньшее значение слева и сверху.

В ячейку R2 запишем: =ЕСЛИ(Q2<R1;Q2+B2;R1+B2)

Скопируем формулу в диапазон R2:AE15.

Например: $R2=10+\min(33;39)=43$. В ячейке AE15 получим минимальную сумму бонусов: $447$.

По условию сначала записывается минимальная сумма, затем максимальная.

Ответ: $447$ $698$.

Код на Python

Если сохранить исходную таблицу в формате CSV с именем 18-05.csv, решение можно записать так:

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-05.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])

Программа выводит:

447 698

В исходном файле таблица занимает диапазон 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$.

По условию сначала записывается минимальная сумма, затем максимальная.

Ответ: $464$ $679$.

Код на 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

В исходном файле таблица занимает диапазон A1:O15, поэтому размер квадрата равен $N=15$.

Внутренних стен в таблице нет, поэтому в каждую клетку, кроме верхней строки и левого столбца, Робот может попасть либо слева, либо сверху.

Расчётную таблицу разместим справа от исходной, начиная с ячейки Q1.

В ячейку Q1 запишем формулу: =СУММ($A$1:A1)

Скопируем её в диапазоны R1:AE1 и Q2:Q15.

Для поиска максимальной суммы в ячейку R2 запишем: =ЕСЛИ(Q2>R1;Q2+B2;R1+B2)

Скопируем формулу в диапазон R2:AE15.

Для первых клеток получаем:

$Q1=20$,
$R1=20+19=39$,
$Q2=20+20=40$,
$R2=25+\max(39;40)=65$.

В ячейке AE15 получим максимальную сумму бонусов: $693$.

Для поиска минимальной суммы в ячейку R2 запишем: =ЕСЛИ(Q2<R1;Q2+B2;R1+B2)

Скопируем формулу в диапазон R2:AE15.

Для первых клеток: $R2=25+\min(39;40)=64$.

В ячейке AE15 получим минимальную сумму бонусов: $454$.

Ответ: $454$ $693$.

Код на Python

Если сохранить исходную таблицу в формате CSV с именем 18-07.csv:

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-07.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])

Программа выводит:

454 693

В исходном файле таблица имеет размер $15\times15$, поэтому $N=15$.

Внутренних стен в таблице нет, поэтому в каждую клетку, кроме верхней строки и левого столбца, Робот может попасть либо слева, либо сверху.

Расчётную таблицу разместим справа от исходной, начиная с ячейки Q1.

В ячейку Q1 запишем: =СУММ($A$1:A1)

Скопируем формулу в диапазоны R1:AE1 и Q2:Q15.

Для поиска максимальной суммы в ячейку R2 запишем: =ЕСЛИ(Q2>R1;Q2+B2;R1+B2)

Скопируем формулу в диапазон R2:AE15.

Для первых клеток получаем:

$Q1=11$,
$R1=11+20=31$,
$Q2=11+23=34$,
$R2=15+\max(31;34)=49$.

В ячейке AE15 получим максимальную сумму бонусов: $697$.

Для поиска минимальной суммы в R2 запишем: =ЕСЛИ(Q2<R1;Q2+B2;R1+B2)

Скопируем формулу в диапазон R2:AE15.

Для первых клеток: $R2=15+\min(31;34)=46$.

В ячейке AE15 получим минимальную сумму бонусов: $407$.

Ответ: $407$ $697$.

Код на Python

Если сохранить исходную таблицу в формате CSV с именем 18-08.csv:

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-08.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])

Программа выводит:

407 697

В исходном файле таблица занимает диапазон 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$.

Ответ: $486$ $707$.

Код на 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

В исходном файле таблица занимает диапазон A1:O15, поэтому размер квадрата равен $N=15$.

Внутренних стен в таблице нет, поэтому в каждую клетку, кроме верхней строки и левого столбца, Робот может попасть либо слева, либо сверху.

Расчётную таблицу разместим справа от исходной, начиная с ячейки Q1.

В ячейку Q1 запишем: =СУММ($A$1:A1)

Скопируем формулу в диапазоны R1:AE1 и Q2:Q15.

Для поиска максимальной суммы в ячейку R2 запишем: =ЕСЛИ(Q2>R1;Q2+B2;R1+B2)

Скопируем формулу в диапазон R2:AE15.

Для первых клеток получаем:

$Q1=19$,
$R1=19+14=33$,
$Q2=19+21=40$,
$R2=15+\max(33;40)=55$.

В ячейке AE15 получим максимальную сумму: $705$.

Для поиска минимальной суммы в ячейку R2 запишем: =ЕСЛИ(Q2<R1;Q2+B2;R1+B2)

Скопируем формулу в диапазон R2:AE15.

Для первых клеток: $R2=15+\min(33;40)=48$.

В ячейке AE15 получим минимальную сумму: $467$.

Ответ: $467$ $705$.

Код на Python

Если сохранить исходную таблицу в формате CSV с именем 18-10.csv:

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-10.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])

Программа выводит:

467 705

В исходном файле таблица имеет размер $15\times15$. Внутренних стен нет, поэтому в каждую клетку Робот может попасть либо слева, либо сверху.

Расчётную таблицу разместим справа от исходной, начиная с ячейки 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+15=33$,
$R2=25+\max(41;33)=66$.

В ячейке AE15 получим максимальную сумму: $678$.

Для поиска минимальной суммы в R2 запишем: =ЕСЛИ(Q2<R1;Q2+B2;R1+B2)

Скопируем формулу в диапазон R2:AE15.

Для первых клеток: $R2=25+\min(41;33)=58$.

В ячейке AE15 получим минимальную сумму: $467$.

Ответ: $467$ $678$.

Код на Python

Если сохранить исходную таблицу в формате CSV с именем 18-11.csv:

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-11.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])

Программа выводит:

467 678

В исходном файле поле имеет размер $20\times20$.

В таблице есть две внутренние стены:

• вертикальная между столбцами F и G на строках $4$–$15$;
• горизонтальная между строками $17$ и $18$ на столбцах L–Q.

Для каждой клетки считаем максимальную сумму: $M_{i,j}=a_{i,j}+\max(M_{i-1,j};M_{i,j-1})$.

Для минимальной суммы: $m_{i,j}=a_{i,j}+\min(m_{i-1,j};m_{i,j-1})$.

Если переход перекрыт стеной, соответствующее значение в формуле не учитываем.

Например, расчётную таблицу можно начать с ячейки V1. Для обычной клетки в W2 при поиске максимума: =B2+МАКС(W1;V2)

Для минимума: =B2+МИН(W1;V2)

Из-за вертикальной стены в ячейках, соответствующих G4:G15, можно приходить только сверху. Например:

=G4+AB3

Из-за горизонтальной стены в ячейках, соответствующих L18:Q18, можно приходить только слева. Например:

=L18+AF18

В правой нижней клетке получаем: максимальная сумма — $2794$; минимальная сумма — $1693$.

Ответ: $2794\ 1693$.

Код на Python

Если сохранить таблицу как 18-12.csv:

a = [
    list(map(int, row.split(';')))
    for row in open('18-12.csv')
]

n = len(a)

# Стена справа от клетки:
# между F и G, строки 4–15
right_wall = {(i, 5) for i in range(3, 15)}

# Стена снизу от клетки:
# между строками 17 и 18, столбцы L–Q
down_wall = {(16, j) for j in range(11, 17)}

INF = 10 ** 9

mn = [[INF] * n for _ in range(n)]
mx = [[-INF] * n for _ in range(n)]

mn[0][0] = mx[0][0] = a[0][0]

for i in range(n):
    for j in range(n):
        if i == 0 and j == 0:
            continue

        p_min = []
        p_max = []

        # Приход сверху
        if i > 0 and (i - 1, j) not in down_wall:
            if mn[i - 1][j] != INF:
                p_min.append(mn[i - 1][j])
                p_max.append(mx[i - 1][j])

        # Приход слева
        if j > 0 and (i, j - 1) not in right_wall:
            if mn[i][j - 1] != INF:
                p_min.append(mn[i][j - 1])
                p_max.append(mx[i][j - 1])

        if p_min:
            mn[i][j] = a[i][j] + min(p_min)
            mx[i][j] = a[i][j] + max(p_max)

print(mx[-1][-1], mn[-1][-1])

Программа выводит:

2794 1693

В исходном файле таблица занимает диапазон $A1:T20$, поэтому размер квадрата равен $N=20$.

В таблице имеются три внутренние стены:

• между столбцами $F$ и $G$ в строках с $4$ по $15$;
• между столбцами $S$ и $T$ в строках со $2$ по $10$;
• между строками $17$ и $18$ в столбцах от $L$ до $Q$.

Расчётную таблицу разместим справа от исходной, начиная с ячейки $V1$. Диапазон $V1:AO20$ будет соответствовать исходному диапазону $A1:T20$.

В ячейку $V1$ запишем: $=A1$

Получим: $V1=107$.

Для первой строки в ячейку $W1$ запишем: $=V1+B1$

Скопируем формулу вправо до ячейки $AO1$.

Для первого столбца расчётной таблицы в ячейку $V2$ запишем: $=V1+A2$

Скопируем формулу вниз до ячейки $V20$.

Для остальных клеток Робот в обычной ситуации может попасть либо слева, либо сверху. Поэтому в ячейку $W2$ запишем: $=B2+МАКС(W1;V2)$

Скопируем эту формулу в диапазон $W2:AO20$.

Для первых клеток получаем:

$V1=107$,
$W1=107+54=161$,
$V2=107+49=156$,
$W2=62+\max(161;156)=223$.

Теперь необходимо учесть внутренние стены.

В строках с $4$ по $15$ Робот не может попасть в клетки столбца $G$ слева из столбца $F$. Значит, в эти клетки можно прийти только сверху.

Столбцу $G$ исходной таблицы соответствует столбец $AB$ расчётной таблицы.

В ячейку $AB4$ запишем:

$=G4+AB3$

Скопируем формулу в диапазон $AB4:AB15$.

Стена между $S$ и $T$

В строках со $2$ по $10$ Робот не может попасть в столбец $T$ из столбца $S$. Следовательно, в клетки $T2:T10$ можно попасть только сверху.

Столбцу $T$ соответствует столбец $AO$ расчётной таблицы.

В ячейку $AO2$ запишем:

$=T2+AO1$

Скопируем формулу в диапазон $AO2:AO10$.

В столбцах от $L$ до $Q$ Робот не может перейти из строки $17$ в строку $18$. Поэтому в клетки $L18:Q18$ можно попасть только слева.

Этим клеткам соответствует диапазон $AG18:AL18$ расчётной таблицы.

В ячейку $AG18$ запишем: $=L18+AF18$

Скопируем формулу вправо в диапазон $AG18:AL18$.

После выполнения расчётов в правой нижней ячейке $AO20$ получим максимальную сумму: $2766$.

Для минимальной суммы используем ту же расчётную таблицу.

Формулы для первой строки, первого столбца и клеток около стен остаются прежними. В обычных клетках вместо максимума выбираем минимальное из двух возможных значений.

В ячейку $W2$ запишем: $=B2+МИН(W1;V2)$

Скопируем формулу в диапазон $W2:AO20$.

После этого снова восстановим специальные формулы около стен:

• в диапазоне $AB4:AB15$: $=G4+AB3$
• в диапазоне $AO2:AO10$: $=T2+AO1$
• в диапазоне $AG18:AL18$: $=L18+AF18$

Для первых клеток: $W2=62+\min(161;156)=218$.

В ячейке $AO20$ получим минимальную сумму: $1820$.

Ответ: $2766$ $1820$.

Код на Python

Если сохранить исходную таблицу без оформления в формате CSV, значения можно обработать программой. Положение стен зададим отдельно.

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-13.csv').read().splitlines()
)

N = len(s)

INF = 10 ** 9

mn = [[INF] * N for _ in range(N)]
mx = [[-INF] * N for _ in range(N)]

mn[0][0] = mx[0][0] = s[0][0]

# В эти клетки нельзя войти слева:
# G4:G15 и T2:T10
blocked_left = (
    {(i, 6) for i in range(3, 15)}
    | {(i, 19) for i in range(1, 10)}
)

# В эти клетки нельзя войти сверху:
# L18:Q18
blocked_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

        mn_prev = []
        mx_prev = []

        if j > 0 and (i, j) not in blocked_left:
            mn_prev.append(mn[i][j - 1])
            mx_prev.append(mx[i][j - 1])

        if i > 0 and (i, j) not in blocked_top:
            mn_prev.append(mn[i - 1][j])
            mx_prev.append(mx[i - 1][j])

        if mn_prev:
            mn[i][j] = s[i][j] + min(mn_prev)
            mx[i][j] = s[i][j] + max(mx_prev)

print(mx[-1][-1], mn[-1][-1])

Программа выводит:

$2766$ $1820$

В исходном файле таблица занимает диапазон $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=105$,
$W1=105+85=190$,
$V2=105+86=191$,
$W2=27+\max(190;191)=218$.

Теперь учтём стены.

Из клеток $F4:F15$ нельзя перейти вправо в $G4:G15$, поэтому в соответствующие клетки можно попасть только сверху. Столбцу $G$ соответствует столбец $AB$ расчётной таблицы.

В ячейку $AB4$ запишем: $=G4+AB3$

Скопируем формулу до $AB15$.

Через стену между строками $17$ и $18$ в столбцах $L:Q$ пройти вниз нельзя. Поэтому в клетки $L18:Q18$ можно попасть только слева.

В ячейку $AG18$ запишем: $=L18+AF18$

Скопируем формулу вправо до $AL18$.

В ячейке $AO20$ получим максимальную сумму: $2852$.

Для поиска минимальной суммы используем ту же таблицу, но в ячейке $W2$ вместо максимума выбираем минимум: $=B2+МИН(W1;V2)$

Скопируем формулу в диапазон $W2:AO20$, после чего снова зададим формулы для клеток около стен: $AB4=G4+AB3$ с копированием до $AB15$, и $AG18=L18+AF18$ с копированием до $AL18$.

Для первых клеток: $W2=27+\min(190;191)=217$.

В ячейке $AO20$ получим минимальную сумму: $1784$.

Ответ: $2852$ $1784$.

Код на Python

Если сохранить исходную таблицу в формате CSV с именем 18-14.csv, задачу можно решить на Python:

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-14.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])

        if a:
            mn[i][j] = s[i][j] + min(a)
            mx[i][j] = s[i][j] + max(b)

print(mx[-1][-1], mn[-1][-1])

Программа выводит:

$2852$ $1784$

Исходная таблица занимает диапазон $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$

В исходном файле таблица занимает диапазон $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=51$,
$W1=51+9=60$,
$V2=51+11=62$,
$W2=90+\max(60;62)=152$.

Теперь учитываем стены. В клетках сразу справа от вертикальной стены оставляем только переход сверху. Такие формулы нужны в диапазонах $X3:X6$, $AE3$, $AG8:AG14$, $AO8:AO14$, $Y14:Y17$, $AM17:AM20$.

Например, в $X3$: $=C3+X2$ а в $AG8$: $=L8+AG7$.

В клетках сразу под горизонтальной стеной оставляем только переход слева. Это диапазоны $AA3:AD3$, $X7:AB7$, $AC15:AF15$, $AL15:AN15$, $AH17:AL17$, $Y18:AC18$.

Например, в $AA3$: $=F3+Z3$

В клетку $N4$ нельзя попасть ни сверху, ни слева, поэтому весь диапазон $N4:Q10$ недостижим. Для максимальной суммы в соответствующий расчётный диапазон $AI4:AL10$ можно записать большое отрицательное значение, например $-10^9$.

Конечными клетками являются $K14$, $S14$, $Q20$ и $T20$. Им соответствуют расчётные ячейки $AF14$, $AN14$, $AL20$, $AO20$.

Для них получаем максимальные суммы:

$AF14=1743$,
$AN14=1996$,
$AL20=2320$,
$AO20=2249$.

Следовательно, максимальная сумма равна: $\max(1743;1996;2320;2249)=2320$.

Для минимальной суммы в обычных клетках вместо функции МАКС используем МИН: $=B2+МИН(W1;V2)$

В недостижимый диапазон $AI4:AL10$ записываем большое положительное значение $10^9$. Формулы около стен остаются такими же.

В конечных клетках получаем:

$AF14=832$,
$AN14=1066$,
$AL20=1207$,
$AO20=1225$.

Минимальная сумма: $\min(832;1066;1207;1225)=832$.

Ответ: $2320$ $832$.

Код на Python

Если сохранить таблицу в формате CSV с именем 18-16.csv, результат можно проверить программой:

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-16.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 == j == 0:
            continue

        a, b = [], []

        if j > 0 and (i, j - 1) not in right:
            a.append(mn[i][j - 1])
            b.append(mx[i][j - 1])

        if i > 0 and (i - 1, j) not in down:
            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_r = j == N - 1 or (i, j) in right
        wall_d = i == N - 1 or (i, j) in down

        if wall_r and wall_d 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))

Программа выводит:

$2320$ $832$

Исходная таблица занимает диапазон $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$.

Ответ: $2598$ $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$

Исходная таблица занимает диапазон $A1:T20$, поэтому $N=20$.

Вертикальные внутренние стены расположены справа от клеток $R3:R5$, $J4:J8$, $D7:D9$, $R10:R18$, $E12:E18$ и $J14:J18$. Горизонтальные стены расположены снизу от $G3:J3$, $O5:R5$, $B9:D9$, $G13:J13$, $D18:E18$ и $L18:R18$.

Расчётную таблицу разместим справа от исходной, начиная с ячейки $V1$. В ячейку $V1$ запишем $=A1$. В ячейку $W1$ запишем $=V1+B1$ и скопируем вправо до $AO1$. В ячейку $V2$ запишем $=V1+A2$ и скопируем вниз до $V20$.

Для поиска максимальной суммы в $W2$ запишем $=B2+МАКС(W1;V2)$ и скопируем формулу в диапазон $W2:AO20$.

Для первых клеток получаем: $V1=52$, $W1=52+1=53$, $V2=52+78=130$, $W2=36+\max(53;130)=166$.

После этого исправим формулы около стен. Справа от вертикальной стены в клетку можно попасть только сверху. Поэтому для диапазонов $S3:S5$, $K4:K8$, $E7:E9$, $S10:S18$, $F12:F18$ и $K14:K18$ используем только значение верхней клетки. Например, в $AN3$ запишем $=S3+AN2$ и скопируем до $AN5$, а в $AF4$ — $=K4+AF3$ и скопируем до $AF8$.

В клетки под горизонтальными стенами можно попасть только слева. Это диапазоны $G4:J4$, $O6:R6$, $B10:D10$, $G14:J14$, $D19:E19$ и $L19:R19$. Например, в $AB4$ запишем $=G4+AA4$ и скопируем вправо до $AE4$.

Конечными являются клетки $R5$, $D9$, $E18$, $R18$ и $T20$. Им соответствуют расчётные ячейки $AM5$, $Y9$, $Z18$, $AM18$ и $AO20$.

Максимальные накопленные суммы в них равны соответственно $1285$, $794$, $1347$, $2353$ и $2507$. Следовательно, максимальная сумма равна $\max(1285;794;1347;2353;2507)=2507$.

Для поиска минимальной суммы в обычных клетках вместо функции МАКС используем МИН: $=B2+МИН(W1;V2)$. Формулы в клетках около стен остаются такими же.

Минимальные суммы в конечных клетках равны $753$, $366$, $1036$, $1117$ и $1479$. Следовательно, минимальная сумма равна $\min(753;366;1036;1117;1479)=366$.

Ответ: $2507$ $366$.

Код на Python

Если сохранить исходную таблицу в формате CSV с именем 18-18.csv, результат можно проверить программой:

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-18.csv').read().splitlines()
)

N = len(s)

right = set()
for r1, r2, c in [
    (3, 5, 18), (4, 8, 10), (7, 9, 4),
    (10, 18, 18), (12, 18, 5), (14, 18, 10)
]:
    for r in range(r1 - 1, r2):
        right.add((r, c - 1))

down = set()
for r, c1, c2 in [
    (3, 7, 10), (5, 15, 18), (9, 2, 4),
    (13, 7, 10), (18, 4, 5), (18, 12, 18)
]:
    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:
            a.append(mn[i][j - 1])
            b.append(mx[i][j - 1])

        if i > 0 and (i - 1, j) not in down:
            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:
            ends.append((mn[i][j], mx[i][j]))

print(max(x[1] for x in ends), min(x[0] for x in ends))

Программа выводит: $2507$ $366$.

Исходная таблица занимает диапазон $A1:T20$, поэтому $N=20$.

Внутренние стены расположены справа от клеток $L3:L12$, $F4:F15$ и снизу от клеток $L17:Q17$.

Расчётную таблицу разместим справа от исходной, начиная с ячейки $V1$.

В ячейку $V1$ запишем: $=A1$

В ячейку $W1$: $=V1+B1$ и скопируем вправо до $AO1$.

В ячейку $V2$: $=V1+A2$ и скопируем вниз до $V20$.

Для поиска максимальной суммы в $W2$ запишем: $=B2+МАКС(W1;V2)$ и скопируем формулу в диапазон $W2:AO20$.

Для первых клеток получаем:

$V1=17$,
$W1=17+71=88$,
$V2=17+45=62$,
$W2=41+\max(88;62)=129$.

Теперь учтём стены. Из-за стены справа от $F4:F15$ в клетки $G4:G15$ можно попасть только сверху. В расчётной таблице это диапазон $AB4:AB15$.

В $AB4$ запишем: $=G4+AB3$ и скопируем до $AB15$.

Из-за стены справа от $L3:L12$ в клетки $M3:M12$ также можно попасть только сверху. В $AH3$ запишем: $=M3+AH2$ и скопируем до $AH12$.

Через стену под $L17:Q17$ нельзя пройти вниз, поэтому в клетки $L18:Q18$ можно попасть только слева.

В $AG18$ запишем: $=L18+AF18$ и скопируем вправо до $AL18$.

В ячейке $AO20$ получим максимальную сумму: $2368$.

Для поиска минимальной суммы в обычных клетках вместо МАКС используем МИН: $=B2+МИН(W1;V2)$

Для первых клеток: $W2=41+\min(88;62)=103$.

Формулы около стен оставляем такими же:

$AB4=G4+AB3$,
$AH3=M3+AH2$,
$AG18=L18+AF18$.

После копирования соответствующих формул в ячейке $AO20$ получим минимальную сумму: $1155$.

Ответ: $2368$ $1155$.

Код на Python

Если сохранить исходную таблицу в формате CSV с именем 18-19.csv, результат можно проверить программой:

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-19.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]

# Стены справа от F4:F15 и L3:L12
wall_left = (
    {(i, 6) for i in range(3, 15)}
    | {(i, 12) for i in range(2, 12)}
)

# Стена снизу от L17:Q17
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])

Программа выводит:

$2368$ $1155$

Исходная таблица занимает диапазон $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=23$,
$W1=23+11=34$,
$V2=23+32=55$,
$W2=14+\max(34;55)=69$.

Около стен оставляем только разрешённое направление движения. Например, справа от стены $B3:B6$ в клетки $C3:C6$ можно попасть только сверху, поэтому в $X3$ запишем: $=C3+X2$ и скопируем до $X6$.

Под стеной $F2:I2$ в клетки $F3:I3$ можно попасть только слева. В $AA3$ запишем: $=F3+Z3$ и скопируем вправо до $AD3$.

Аналогично учитываем остальные стены. Диапазон $N4:Q10$ недостижим, поэтому при поиске максимума соответствующему диапазону $AI4:AL10$ зададим большое отрицательное значение, например $-10^9$.

Конечными клетками являются $K14$, $S14$, $Q20$ и $T20$. Им соответствуют ячейки $AF14$, $AN14$, $AL20$, $AO20$.

Максимальные суммы в них:

$AF14=1671$,
$AN14=2167$,
$AL20=2361$,
$AO20=2340$.

Следовательно, $\max(1671;2167;2361;2340)=2361$.

Для поиска минимальной суммы в обычных клетках используем: $=B2+МИН(W1;V2)$

Для первых клеток: $W2=14+\min(34;55)=48$.

В недостижимый диапазон $AI4:AL10$ записываем большое положительное значение $10^9$. Формулы около стен остаются такими же.

Минимальные суммы в конечных клетках: $AF14=980$, $AN14=1206$, $AL20=907$, $AO20=1315$.

Следовательно, $\min(980;1206;907;1315)=907$.

Ответ: $2361$ $907$.

Код на Python

Если сохранить таблицу в формате CSV с именем 18-20.csv, результат можно проверить программой:

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-20.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))

Программа выводит: $2361$ $907$.