Какой маршрут имеет самую высокую стоимость? Черепашка находится в левом верхнем углу прямоугольной таблицы размером

Сквозь_Лес

34

Максимальное значение суммы и соответствующий маршрут можно найти с использованием динамического программирования.

Для начала создадим прямоугольную таблицу размером N × M, где каждая ячейка будет хранить текущую максимальную сумму чисел, достигнутую черепашкой при достижении этой ячейки.

Пусть dp[i][j] будет представлять максимальную сумму чисел, достигнутую черепашкой при достижении ячейки (i, j). Тогда мы можем рассчитывать значения dp[i][j] следующим образом:

1. Для первой строка таблицы (i = 0) достижение ячейки (0, j) возможно только двигаясь вправо от предыдущей ячейки. Таким образом, dp[0][j] = dp[0][j-1] + grid[0][j], где grid[i][j] - значение, записанное в ячейке (i, j).

2. Для первого столбца таблицы (j = 0) достижение ячейки (i, 0) возможно только двигаясь вниз от предыдущей ячейки. Таким образом, dp[i][0] = dp[i-1][0] + grid[i][0].

3. Для остальных ячеек таблицы, достижение ячейки (i, j) возможно либо двигаясь вниз от предыдущей ячейки (dp[i-1][j] + grid[i][j]), либо двигаясь вправо от предыдущей ячейки (dp[i][j-1] + grid[i][j]). Выбираем путь с максимальной суммой чисел и обновляем значение dp[i][j] соответственно.

4. Максимальная сумма чисел, достигнутая черепашкой, будет храниться в ячейке dp[N-1][M-1].

Теперь рассмотрим путь, соответствующий этой максимальной сумме чисел. Мы можем его построить, следуя обратно от ячейки (N-1, M-1) к ячейке (0, 0) по следующему правилу: если значение dp[i][j] должно быть обновлено при движении вниз, значит черепашка двигалась вниз, иначе - вправо. Запоминаем каждое такое движение и получаем искомый маршрут.

Приведенный ниже код демонстрирует решение с использованием описанного алгоритма:

python

def find_maximum_sum_path(N, M, grid):

    # Создаем таблицу dp размером N x M

    dp = [[0] * M for _ in range(N)]

    # Создаем таблицу для хранения маршрута

    directions = [[""] * M for _ in range(N)]



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

    for j in range(1, M):

        dp[0][j] = dp[0][j-1] + grid[0][j]

        directions[0][j] = "R"



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

    for i in range(1, N):

        dp[i][0] = dp[i-1][0] + grid[i][0]

        directions[i][0] = "D"



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

    for i in range(1, N):

        for j in range(1, M):

            if dp[i-1][j] + grid[i][j] >= dp[i][j-1] + grid[i][j]:

                dp[i][j] = dp[i-1][j] + grid[i][j]

                directions[i][j] = "D"

            else:

                dp[i][j] = dp[i][j-1] + grid[i][j]

                directions[i][j] = "R"



    # Получаем максимальную сумму чисел

    max_sum = dp[N-1][M-1]



    # Восстанавливаем маршрут

    path = []

    i, j = N-1, M-1

    while i > 0 or j > 0:

        path.append((i, j))

        if directions[i][j] == "D":

            i -= 1

        else:

            j -= 1

    path.append((0, 0))

    path.reverse()



    return max_sum, path

Эта функция может быть вызвана следующим образом:

python

N, M = map(int, input().split())

grid = []

for _ in range(N):

    row = list(map(int, input().split()))

    grid.append(row)



max_sum, path = find_maximum_sum_path(N, M, grid)

print("Максимальная сумма чисел:", max_sum)

print("Маршрут достигающий этой суммы:")

for i, j in path:

    print(f"({i}, {j})")

Этот код находит максимальную сумму чисел, которую может достичь черепашка, а также выводит маршрут, соответствующий этой сумме.