Question

Python Вывести маршрут максимальной стоимости В левом верхнем углу прямоугольной таблицы размером N×M находится черепашка. В каждой клетке таблицы записано некоторое число. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы. Подсчитаем сумму чисел, записанных в клетках, через которую проползла черепашка (включая начальную и конечную клетку). Найдите наибольшее возможное значение этой суммы и маршрут, на котором достигается эта сумма. Входные данные В первой строке входных данных записаны два натуральных числа N и M, не превосходящих 100 — размеры таблицы. Далее идут N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100. Выходные данные Первая строка выходных данных содержит максимальную возможную сумму, вторая — маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N−1 букву D, означающую передвижение вниз и M−1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.

Answer 1

Объяснение:

Эта задача сводится к задаче поиска пути на графе пространства состояний.

Состояние - положение черепашки на поле - (x, y).

Граф пространства состояний состоит из таких вершин-состояний, их количество N * M.

Переходов между вершинами всего два: R и D.

Здесь можно заметить, что прийти к одним и тем же вершинам мы можем разными путями. Например, путь из (0,0) в (1,1) можно расписать и как RD ((0,0) -> (0,1) -> (1,1)), и как DR ((0,0) -> (1,0) -> (1,1)), но это два разных маршрута.

Однако при неизменном ценовом листе максимальная стоимость и оный маршрут в любой клетке поля значение строго определённое и неизменное во времени.

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

Итак, для каждого состояния у нас есть два правила перехода. Рассчитывая максимальную стоимость маршрута для состояния (x,y) мы следуем алгоритму:

1. Если можем идти вправо, рассчитываем параметры для этого маршрута
2. Если можем идти вниз, рассчитываем параметры для этого маршрута
3. Выбираем между путями, если можем идти, или стоим, если уже не можем
4. К выбранному варианту добавляем параметры текущего состояния

Если такой алгоритм применить к состоянию (0,0), то дойдем до (N, M) и получим максимальную цену и маршрут.

Код:

import re

from typing import List

cache = {}

def calculate_max_way_price(x: int, y: int, prices: List[List[int]], m:int, n:int):

   if (x, y) in cache:

       return cache[(x, y)]

   direction = ''

   cost = prices[y][x]

   x_cost, y_cost = -1, -1

   x_way, y_way = '', ''

   if x < m - 1:

       x_cost, x_way = calculate_max_way_price(x + 1, y, prices, m, n)

   if y < n - 1:

       y_cost, y_way = calculate_max_way_price(x, y + 1, prices, m, n)

   if not (x_cost < 0 and y_cost < 0):

       if x_cost > y_cost:

           cost += x_cost

           direction = 'R' + x_way

       else:

           cost += y_cost

           direction = 'D' + y_way

   cache[(x, y)] = (cost, direction)

   return cost, direction

MNtext = input('Enter N M: ')

MN = [int(x) for x in re.findall(r'\d+', MNtext)]

if len(MN) != 2:

   print("Input data error! It is not M and N")

   exit(-1)

N, M = MN[0], MN[1]

MAX_STEP_PRICE = 100

data = input('Enter all numbers separated by spaces. You must type ' + str(M*N) + ' elements:')

data = [int(x) for x in re.findall(r'\d+', data)]

if len(data) != N * M:

   print("Input data error! Too few/many numbers")

   exit(-2)

prices = []

for j in range(N):

   prices.append(data[M*j:M*(j+1)])

print(calculate_max_way_price(0, 0, prices, M, N))

Answer 2

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

1. Инициализируем `dp[0][0]` значением из левого верхнего угла таблицы.

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

3. Для остальных клеток `(i, j)` массива `dp`, заполняем их значением как `max(dp[i-1][j], dp[i][j-1]) + table[i][j]`, где `table[i][j]` - значение в клетке `(i, j)` из таблицы.

После заполнения `dp`, значение `dp[N-1][M-1]` будет содержать максимальную сумму, а теперь нужно восстановить маршрут, на котором достигается это значение. Для этого начнем с клетки `(N-1, M-1)` и будем двигаться в обратном направлении, выбирая путь с максимальными значениями `dp`.

Вот Python-код, который решает эту задачу:

N, M = map(int, input().split())
table = []
for _ in range(N):
    row = list(map(int, input().split()))
    table.append(row)

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

# Заполняем первую строку и первый столбец
for i in range(1, N):
    dp[i][0] = dp[i-1][0] + table[i][0]
for j in range(1, M):
    dp[0][j] = dp[0][j-1] + table[0][j]

# Заполняем остальные клетки
for i in range(1, N):
    for j in range(1, M):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + table[i][j]

# Восстанавливаем маршрут
i, j = N - 1, M - 1
path = []
while i > 0 or j > 0:
    path.append('D' if i > 0 and dp[i][j] - table[i][j] == dp[i-1][j] else 'R')
    if i > 0 and dp[i][j] - table[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1

path.reverse()

# Выводим результат
print(dp[N-1][M-1])
print(''.join(path))

Этот код сначала заполняет массив `dp`, затем восстанавливает маршрут, начиная с клетки `(N-1, M-1)`, и выводит максимальную сумму и маршрут.