Какое количество золота собрал мудрец, пройдя по заданному маршруту в комнате размером n×m клеток, где каждая клетка

Пугающий_Пират

51

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

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

Теперь, для каждой остальной клетки (i, j), где i>1 и j>1, мы можем найти максимальное количество золота на основе значения предыдущих клеток. Для этого сравним два пути: один идет из клетки сверху (i-1, j), а другой идет из клетки слева (i, j-1). Мы выбираем путь с максимальным количеством золота и добавляем его к золоту в текущей клетке (i, j). Таким образом, максимальное количество золота для клетки (i, j) будет равно золоту в этой клетке плюс максимальное количество золота из двух предыдущих путей.

После заполнения всей таблицы, максимальное количество золота, собранное мудрецом, будет находиться в последней клетке (n, m). Давайте реализуем этот алгоритм в коде на Python:

python

def count_max_gold(n, m, grid):

    # Создаем таблицу для хранения максимального золота

    max_gold = [[0] * m for _ in range(n)]



    # Заполняем первую строку

    for j in range(m):

        max_gold[0][j] = sum(grid[0][:j+1])



    # Заполняем первый столбец

    for i in range(n):

        max_gold[i][0] = sum(grid[k][0] for k in range(i+1))



    # Заполняем остальные клетки

    for i in range(1, n):

        for j in range(1, m):

            max_gold[i][j] = grid[i][j] + max(max_gold[i-1][j], max_gold[i][j-1])



    # Возвращаем максимальное количество золота

    return max_gold[n-1][m-1]



# Считываем размеры комнаты

n, m = map(int, input().split())



# Считываем количество золота в каждой клетке

grid = [list(map(int, input().split())) for _ in range(n)]



# Вызываем функцию для подсчета максимального количества золота

result = count_max_gold(n, m, grid)



# Выводим результат

print(result)

Этот код принимает входные данные, создает таблицу и заполняет ее на основе описанного алгоритма. Затем он выводит максимальное количество золота, собранное мудрецом, после прохождения по заданному маршруту в комнате.

Надеюсь, это поможет вам понять решение задачи. Если у вас есть дополнительные вопросы, не стесняйтесь задавать!