Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

18. Исполнитель Робот: Квадрат разлинован на N× N клеток (1<N<30)

Задание #297202
Решено верно
Решено неверно
Сообщить о проблеме

Квадрат разлинован на $N\times N$ клеток ($1<N<30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от $1$ до $100$. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.

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

Исходные данные представляют собой электронную таблицу размером $N\times N$, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.

Пример входных данных:

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

Код на 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
Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение