Question

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

В каждой клетке лежит монета достоинством от 1 до 100. Робот забирает монету при посещении клетки (включая начальную и конечную). В «угловых» клетках, ограниченных стенами справа и снизу, Робот не может продолжать движение, и накопленная сумма считается итоговой. Таких конечных клеток может быть несколько, включая правую нижнюю клетку.

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

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

Accepted Answer

2400 852

Answer

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

Подход состоит из следующих этапов:

1. **Инициализация таблиц динамики.** Создаём две таблицы размером $N 	imes N$: одну для максимальных сумм, другую для минимальных. Начальное значение в левой верхней клетке равно стоимости монеты в этой клетке.

2. **Заполнение первой строки и первого столбца.** Для клеток первой строки (кроме начальной) сумма равна сумме текущей монеты и значения из левой клетки (если нет стены слева). Для клеток первого столбца (кроме начальной) сумма равна сумме текущей монеты и значения из верхней клетки (если нет стены сверху).

3. **Заполнение остальных клеток.** Для каждой клетки $(i, j)$:
   - Если слева есть стена, сумма вычисляется только из верхней клетки.
   - Если сверху есть стена, сумма вычисляется только из левой клетки.
   - Если стен нет, берём максимум (или минимум) из двух соседних клеток и добавляем текущую монету.

4. **Поиск ответа.** Среди всех угловых клеток (клеток, из которых нельзя продолжить движение) находим максимальное и минимальное значения.

Пример реализации на Python с использованием pandas:

```python
import pandas as pd

df = pd.read_excel("18.xlsx", header=None)
N = df.shape[0]

# Таблица для максимальных сумм
dp_max = [[0] * N for _ in range(N)]
dp_max[0][0] = df.iat[0, 0]

# Заполнение первой строки
for j in range(1, N):
    dp_max[0][j] = dp_max[0][j-1] + df.iat[0, j]

# Заполнение первого столбца
for i in range(1, N):
    dp_max[i][0] = dp_max[i-1][0] + df.iat[i, 0]

# Заполнение остальных клеток
for i in range(1, N):
    for j in range(1, N):
        dp_max[i][j] = df.iat[i, j] + max(
            dp_max[i-1][j],
            dp_max[i][j-1]
        )

# Аналогично для минимальных сумм
dp_min = [[0] * N for _ in range(N)]
dp_min[0][0] = df.iat[0, 0]

for j in range(1, N):
    dp_min[0][j] = dp_min[0][j-1] + df.iat[0, j]

for i in range(1, N):
    dp_min[i][0] = dp_min[i-1][0] + df.iat[i, 0]

for i in range(1, N):
    for j in range(1, N):
        dp_min[i][j] = df.iat[i, j] + min(
            dp_min[i-1][j],
            dp_min[i][j-1]
        )

# Поиск максимальной и минимальной сумм среди конечных клеток
max_sum = dp_max[N-1][N-1]
min_sum = dp_min[N-1][N-1]

print(max_sum, min_sum)
```

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

Задание №18Информационные модели и структуры данныхЕГЭ по информатике