Question

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

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

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

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

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

| 1 | 8 | 8 | 4 |
|---|---|---|---|
| 10 | 1 | 1 | 3 |
| 1 | 3 | 12 | 2 |
| 2 | 3 | 5 | 6 |

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

Accepted Answer

10991026

Answer

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

**Шаг 1. Инициализация таблиц динамики.**

Создадим две таблицы: `dp_max` для максимальной суммы и `dp_min` для минимальной суммы. Каждая таблица имеет размер $N 	imes N$.

**Шаг 2. Заполнение первой строки и первого столбца.**

Для первой строки (верхний край): каждая ячейка содержит сумму всех ячеек слева от неё (если нет стены слева). Для первого столбца (левый край): каждая ячейка содержит сумму всех ячеек сверху от неё (если нет стены сверху).

**Шаг 3. Заполнение остальных ячеек.**

Для каждой ячейки $(i, j)$:
- Если слева есть стена, значение берётся только сверху: `dp[i][j] = dp[i-1][j] + value[i][j]`.
- Если сверху есть стена, значение берётся только слева: `dp[i][j] = dp[i][j-1] + value[i][j]`.
- Если стен нет, берётся максимум (для `dp_max`) или минимум (для `dp_min`) из двух соседей: `dp[i][j] = value[i][j] + max(dp[i-1][j], dp[i][j-1])` или `dp[i][j] = value[i][j] + min(dp[i-1][j], dp[i][j-1])`.

**Шаг 4. Определение стен.**

Стены определяются по утолщённым линиям в таблице. Для каждой ячейки проверяются границы: есть ли стена сверху (между текущей и верхней ячейкой) и слева (между текущей и левой ячейкой).

**Шаг 5. Вывод результата.**

Ответ находится в ячейке `dp_max[N-1][N-1]` и `dp_min[N-1][N-1]`.

```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_min = [[0] * N for _ in range(N)]

# Начальная ячейка
dp_max[0][0] = df.iat[0, 0]
dp_min[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]
    dp_min[0][j] = dp_min[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]
    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):
        current = df.iat[i, j]
        dp_max[i][j] = current + max(dp_max[i-1][j], 
                                      dp_max[i][j-1])
        dp_min[i][j] = current + min(dp_min[i-1][j], 
                                      dp_min[i][j-1])

print(dp_max[N-1][N-1], dp_min[N-1][N-1])
```

Сложность: $O(N^2)$.

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