В.Н. Шубинкин, г. Казань) В любой клетке поля может быть стена (стены обозначены значениями больше 100, но меньше 500) или яма (ямы обозначены значениями меньше 0, но больше -400). Робот может двигаться только вниз или вправо. При попытке зайти на клетку со стеной Робот разрушается. При попытке зайти на клетку с ямой Робот застревает в ней и не может двигаться дальше.
Исходные данные записаны в файле 18-13.xls в виде электронной таблицы прямоугольной формы. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю, не разрушившись и не застряв в яме. Известно, что такой путь существует. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Для решения задачи, которую вы описали, необходимо рассмотреть алгоритмы, которые позволят роботу двигаться по заданной сетке и находить максимальную и минимальную сумму денег, при этом избегая стен и ям.
Так как движения робота допускаются только вниз и вправо, мы можем использовать методы динамического программирования. Давайте разберем решение пошагово:
### Шаг 1: Подготовка данных
1. Откройте файл `18-13.xls` и проверьте, в каком виде представлено поле.
2. Переведите значения в матрицу, где:
- Стены (значения от 101 до 499) — обозначаем как `None` или `-inf` для максимальной суммы.
- Ямы (значения от -1 до -399) — обозначаем как `None` или `-inf` для максимальной суммы.
- Остальные клетки с деньгами — оставляем значения как есть.
### Шаг 2: Алгоритм для нахождения максимальной суммы
- Создадим двумерный массив `max_sum` такого же размера, как и исходное поле, где `max_sum[i][j]` будет хранить максимальную сумму, которую робот может собрать, достигая клетки `(i, j)`.
- Начнем с инициализации:
- `max_sum[0][0] = grid[0][0]` (если в клетке нет стены или ямы).
- Заполним первую строку и первый столбец, учитывая, что робот может двигаться только вправо и вниз.
- Далее для всех остальных клеток вычисляем максимальную сумму:
- Если клетка не стена и не яма, обновляем `max_sum[i][j]` как `max(max_sum[i-1][j], max_sum[i][j-1]) + grid[i][j]`.
### Шаг 3: Алгоритм для нахождения минимальной суммы
- Аналогично создадим массив `min_sum` для хранения минимальных сумм.
- Инициализируем первую клетку и заполним первую строку и первый столбец по аналогии, но на этот раз будем брать минимальные значения:
- Полное заполнение будет выглядеть как `min(min_sum[i-1][j], min_sum[i][j-1]) + grid[i][j]`.
### Шаг 4: Получение ответов
- По окончании заполнения массивов `max_sum` и `min_sum`, максимальная сумма будет в правом нижнем углу `max_sum[n-1][m-1]`, а минимальная — в `min_sum[n-1][m-1]`.
### Пример кода на Python:
После окончания вышеизложенных шагов, вот примерный код, который выполняет необходимые операции:
```python
import pandas as pd
# Загружаем данные из excel файла
df = pd.read_excel('18-13.xls')
grid = df.values
n = len(grid)
m = len(grid[0])
# Инициализация массивов для максимальной и минимальной суммы
max_sum = [[0] * m for _ in range(n)]
min_sum = [[0] * m for _ in range(n)]
# Начальные условия
max_sum[0][0] = grid[0][0] if grid[0][0] <= 100 else float('-inf')
min_sum[0][0] = grid[0][0] if grid[0][0] <= 100 else float('inf')
# Заполнение первой строки
for j in range(1, m):
if grid[0][j] <= 100:
max_sum[0][j] = max_sum[0][j-1] + grid[0][j]
min_sum[0][j] = min_sum[0][j-1] + grid[0][j]
else:
max_sum[0][j] = float('-inf')
min_sum[0][j] = float('inf')
# Заполнение первого столбца
for i in range(1, n):
if grid[i][0] <= 100:
max_sum[i][0] = max_sum[i-1][0] + grid[i][0]
min_sum[i][0] = min_sum[i-1][0] + grid[i][0]
else:
max_sum[i][0] = float('-inf')
min_sum[i][0] = float('inf')
# Заполнение остальных клеток
for i in range(1, n):
for j in range(1, m):
if grid[i][j] <= 100:
max_sum[i][j] = max(max_sum[i-1][j], max_sum[i][j-1]) + grid[i][j]
min_sum[i][j] = min(min_sum[i-1][j], min_sum[i][j-1]) + grid[i][j]
else:
max_sum[i][j] = float('-inf')
min_sum[i][j] = float('inf')
# Итоговые значения
max_value = max_sum[n-1][m-1]
min_value = min_sum[n-1][m-1]
print(max_value, min_value)
```
### Заключение
В результате выполнения приведенного кода вы получите максимальную и минимальную сумму, которую робот может собрать, двигаясь по сетке в соответствии с указанными правилами. Убедитесь, что вы корректно адаптировали код к формату вашего файла.
