Python

Вывести маршрут максимальной стоимости

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

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

Входные данные

В первой строке входных данных записаны два натуральных числа N
и M
, не превосходящих 100
— размеры таблицы. Далее идут N
строк, каждая из которых содержит M
чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0
до 100
.

Выходные данные

Первая строка выходных данных содержит максимальную возможную сумму, вторая — маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N−1
букву D, означающую передвижение вниз и M−1
букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.
Примеры:
Ввод
5 5
9 9 9 9 9
3 0 0 0 0
9 9 9 9 9
6 6 6 6 8
9 9 9 9 9
Вывод
74
D D R R R R D D
Подсчёт стоимости я сделал, осталось только буквы выстроить
 n, m = map(int, input().split()) 

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

a = [[0]*m for i in range(n)] 

letters = [] 

x = len(a) 

i = len(a[0]) 

a[0][0] = p[0][0] 

for x in range(1, m): 

    a[0][x] = a[0][x - 1] + p[0][x] 

for x in range(1, n): 

    a[x][0] = a[x - 1][0] + p[x][0] 

for x in range(1, n): 

    for i in range(1, m): 

        a[x][i] = max(a[x - 1][i], a[x][i - 1]) + p[x][i] 

 

letters = letters[::-1] 

print(a[-1][-1]) 

print(' '.join(letters))
Рома Лев
Рома Лев
103
Проще всего в каждую клетку добавить не только стоимость, но и маршрут:
 n, m = map(int, input().split())

a = [[[int(v), ''] for v in input().split()] for _ in range(n)]

for i in range(1, m):

  a[0][i][0] += a[0][i - 1][0]

  a[0][i][1] = a[0][i - 1][1] + 'R'

for i in range(1, n):

  a[i][0][0] += a[i - 1][0][0]

  a[i][0][1] = a[i - 1][0][1] + 'D'

for i in range(1, n):

  for j in range(1, m):

    if a[i][j - 1][0] > a[i - 1][j][0]:

      a[i][j][0] += a[i][j - 1][0]

      a[i][j][1] = a[i][j - 1][1] + 'R'

    else:

      a[i][j][0] += a[i - 1][j][0]

      a[i][j][1] = a[i - 1][j][1] + 'D'

print(a[-1][-1][0])

print(*a[-1][-1][1])
Владимир Кочергин
Владимир Кочергин
87 720
Лучший ответ
Гаджи Габибулаев можете,пожалуйста,написать маршрут отдельно, не вместе со стоимостью. 
 n, m = map(int, input().split())  p = [list(map(int, input().split())) for i in range(n)]  

a = [[0]*m for i in range(n)]  

letters = []  

x = len(a)  

i = len(a[0])  

a[0][0] = p[0][0]  

for x in range(1, m):  

    a[0][x] = a[0][x - 1] + p[0][x]  

for x in range(1, n):  

    a[x][0] = a[x - 1][0] + p[x][0]  

for x in range(1, n):  

    for i in range(1, m):  

        a[x][i] = max(a[x - 1][i], a[x][i - 1]) + p[x][i]  

while x > 0 and i > 0:  

    if a[x - 1][i] > a[x][i - 1]:  

        letters.append("D")  

        x -= 1  

    else:  

        letters.append("R")  

        i -= 1  

while x > 0:  

    letters.append("D")  

    x -= 1  

while i > 0:  

    letters.append("R")  

    i -= 1  

letters = letters[::-1]  

print(a[-1][-1])  

print(' '.join(letters))
Николай Из Курска
Николай Из Курска
8 642
Рома Лев Прости но пишет программа выдаёт ошибку в процессе выполнения
Рома Лев Он не пишет про код ошибки
Рома Лев Спасибо, я сам попробую 
 import random 

 

n, m = 10, 10 

 

a = [[random.randint(0,100) for i in range (m)] for j in range(n)] 

w = [[0 for i in range (m)] for j in range(n)] 

 

def calc_way(way): 

    x, y = 0, 0 

    sum1 = 0 

    sum1 += a[x][y] 

    for i in way: 

        if i == '0': 

            x += 1 

        if i == '1': 

            y += 1 

        sum1 += a[y][x] 

    return sum1 

 

def show_way(way): 

    x, y = 0, 0 

    w[y][x] = 1 

    for i in way: 

        if i == '0': 

            x += 1 

        if i == '1': 

            y += 1 

        w[y][x] = 1 

 

max_sum = 0 

way = '' 

 

for i in range(2**(n+m-2)): 

 

    s1 = '0'+str(n+m-2)+'b' 

    b=format(i,s1)     

 

    if b.count('1') != n-1: 

        continue 

    sum1 = calc_way(b) 

    if sum1 > max_sum: 

        max_sum = sum1 

        way = b 

 

show_way(way) 

 

print(n,m) 

 

# draw array 

for i in range(n): 

    for j in range(m): 

        if w[i][j] == 1: 

            print(f'{a[i][j]:3d}',end='*') 

        else: 

            print(f'{a[i][j]:3d}',end=' ') 

    print() 

 

#print result 

print(max_sum) 

 

#print way 

for i in way: 

    if i == '0': 

        print('R ', end='') 

    if i == '1': 

        print('D ', end='')
Владимир Вислогузов
Владимир Вислогузов
315

Похожие вопросы