Задание №18 — Задачи на динамику для таблиц

Решение:

Робот ходит только вправо и вниз, поэтому в любую клетку он приходит либо сверху, либо слева и ни одной клетки не проходит дважды. Значит, работает динамическое программирование: для каждой клетки достаточно хранить максимальную и минимальную суммы, которые можно накопить, дойдя до неё из левой верхней клетки.

Пусть $a_{ij}$ — номинал монеты в клетке, $M_{ij}$ и $m_{ij}$ — максимальная и минимальная накопленные суммы. Тогда $M_{ij}=\max(M_{i-1,j},\,M_{i,j-1})+a_{ij}$ и $m_{ij}=\min(m_{i-1,j},\,m_{i,j-1})+a_{ij}$, причём соседняя клетка учитывается только тогда, когда между ней и текущей нет стены. Для левой верхней клетки $M_{11}=m_{11}=a_{11}$.

В приложенном файле поле имеет размер $20\times20$, стены показаны утолщёнными линиями. Вертикальные внутренние стены (движение вправо запрещено) стоят:

• между 2-м и 3-м столбцами — в строках 2–8;
• между 4-м и 5-м столбцами — в строках 5–13;
• между 6-м и 7-м столбцами — в строках 10–18;
• между 9-м и 10-м столбцами — в строках 2–9;
• между 12-м и 13-м столбцами — в строках 6–14;
• между 15-м и 16-м столбцами — в строках 9–18.

Горизонтальные внутренние стены (движение вниз запрещено) стоят между 2-й и 3-й строками в столбцах 4–8 и между 17-й и 18-й строками в столбцах 9–14.

Скопируем содержимое таблицы в текстовый файл 18.txt (числа разделены пробелами или знаками табуляции) и обработаем его программой.

f = open('18.txt')
a = [[int(x) for x in s.split()] for s in f]
N = len(a)

# стена снизу от клетки (i, j); строки и столбцы нумеруются с нуля
def wall_down(i, j):
    return (i == 1 and 3 <= j <= 7) or (i == 16 and 8 <= j <= 13)

# стена справа от клетки (i, j)
def wall_right(i, j):
    return ((j == 1 and 1 <= i <= 7) or (j == 8 and 1 <= i <= 8) or
            (j == 3 and 4 <= i <= 12) or (j == 11 and 5 <= i <= 13) or
            (j == 5 and 9 <= i <= 17) or (j == 14 and 8 <= i <= 17))

MX = [[0] * N for i in range(N)]   # максимум, накопленный к клетке
MN = [[0] * N for i in range(N)]   # минимум
for i in range(N):
    for j in range(N):
        if i == 0 and j == 0:
            MX[i][j] = MN[i][j] = a[0][0]
            continue
        v = []
        if i > 0 and not wall_down(i - 1, j):
            v.append((MX[i - 1][j], MN[i - 1][j]))
        if j > 0 and not wall_right(i, j - 1):
            v.append((MX[i][j - 1], MN[i][j - 1]))
        MX[i][j] = max(x for x, y in v) + a[i][j]
        MN[i][j] = min(y for x, y in v) + a[i][j]

print(MX[N - 1][N - 1], MN[N - 1][N - 1])

Программа выводит 1099 1026: максимальная сумма равна 1099, минимальная — 1026. Ответ: 1099 1026