В.Н. Шубинкин, г. Казань) В любой клетке поля может быть стена (стены обозначены значениями больше 100, но меньше 500) или яма (ямы обозначены значениями меньше 0, но больше…

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

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

Шаг 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:

После окончания вышеизложенных шагов, вот примерный код, который выполняет необходимые операции:

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)

Заключение

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