Вывести маршрут максимальной стоимости (модифицировать)

@DMustache · Регистрация: 25.07.2020

Студворк — интернет-сервис помощи студентам

Вывести маршрут максимальной стоимости
В левом верхнем углу прямоугольной таблицы размером 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

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
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)]
a[0][0] = p[0][0]
 
for j in range(1, m):
    a[0][j] = a[0][j - 1] + p[0][j]
for i in range(1, n):
    a[i][0] = a[i - 1][0] + p[i][0]
for i in range(1, n):
    for j in range(1, m):
        a[i][j] = max(a[i][j -1], a[i - 1][j]) + p[i][j]
print(a[-1][-1])

Помогите пожалуйста его модифицировать

Добавлено через 3 часа 50 минут
сори за говнокод, сейчас выложу более читабельный

Добавлено через 32 минуты
Вот более читабельный код

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
y, x = map(int, input().split())
location =[list(map(int, input().split())) for i in range(y)]  #список цен за проход
cost = [[0] * x for i in range(y)]  #список затрат
cost[0][0] = location[0][0]
 
for Xelem in range(1, x):
    cost[0][Xelem] = cost[0][Xelem - 1] + location[0][Xelem]
    #заполнение первой строчки
 
for Yelem in range(1, y):
    cost[Yelem][0] = cost[Yelem - 1][0] + location[Yelem][0]
    #заполнение первого столбца
 
for Yelem in range(1, y):
    for Xelem in range(1, x):
        cost[Yelem][Xelem] = max(cost[Yelem][Xelem -1], cost[Yelem - 1][Xelem]) + location[Yelem][Xelem]
        #заполнение всех ячеек
 
print(cost[-1][-1])

@Gdez · 01.08.2020, 20:01

В рамках условий прокатит и этот :

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)]
b = [[''] * m for i in range(n)]
a[0][0] = p[0][0]
for j in range(1, m):
    a[0][j] = a[0][j - 1] + p[0][j]
    b[0][j] = b[0][j-1] + 'R'
for i in range(1, n):
    a[i][0] = a[i - 1][0] + p[i][0]
    b[i][0] = b[i - 1][0] + 'D'
for i in range(1, n):
    for j in range(1, m):
        if a[i][j -1] > a[i - 1][j] :
            a[i][j] = a[i][j -1] + p[i][j]
            b[i][j] = b[i][j -1] + 'R'
        else :
            a[i][j] = a[i-1][j] + p[i][j]
            b[i][j] = b[i-1][j] + 'D'
print(a[-1][-1])
print(b[-1][-1])

Но при больших "n" и "m" может не пройти.
А поиск алгоритма для больших данных прост - распечатай значения массива "а" и увидишь, что необходимо поднятся снизу с последней клетки вверх по максимальным значениям соседних клеток, только наоборот - справа налево и снизу вверх...
Кстати, тут на форуме куча готовых решений и намного лучше моего

@DMustache · 02.08.2020, 18:12 **[ТС]**

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
y, x = map(int, input().split())
location =[list(map(int, input().split())) for i in range(y)]
cost = [[0] * x for i in range(y)]
road = [[""] * x for i in range(y)]
cost[0][0] = location[0][0]
 
for Xelem in range(1, x):
    cost[0][Xelem] = cost[0][Xelem - 1] + location[0][Xelem]
    road[0][Xelem] = road[0][Xelem - 1] + 'R'
 
for Yelem in range(1, y):
    cost[Yelem][0] = cost[Yelem - 1][0] + location[Yelem][0]
    road[Yelem][0] = road[Yelem - 1][0] + 'D'
 
for Yelem in range(1, y):
    for Xelem in range(1, x):
        cost[Yelem][Xelem] = max(cost[Yelem][Xelem -1], cost[Yelem - 1][Xelem]) + location[Yelem][Xelem]
        if cost[Yelem][Xelem - 1] > cost[Yelem - 1][Xelem] :
            road[Yelem][Xelem] = road[Yelem][Xelem - 1] + 'R'
        else :
            road[Yelem][Xelem] = road[Yelem - 1][Xelem] + 'D'
print(cost[-1][-1])
print(road[-1][-1])

вот так получилось дополнить код с помощью пользователя сверху

@DenisSimahin · 10.07.2024, 18:53

Вот мой код на эту тему, помогите, понять в чем моя ошибка, почему не выводит некоторые необходимые данные

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
n,m=map(int, input().split())
a=[list(map(int, input().split())) for i in range(n)]
need=[[0]*m for i in range(n)]
need[0][0]=a[0][0]
for j in range(1,m):
  need[0][j]=need[0][j-1]+a[0][j]
for i in range(1,n):
    need[i][0]=need[i-1][0]+a[i][0]
for i in range(1,n):
  for j in range(1,m):
    need[i][j]=max(need[i][j-1], need[i-1][j])+a[i][j]
print(need[-1][-1])
strr=''
i, j = n-1, m-1
print (i, j)
while i!=0 and j!=0:
    if j!=0:
        if need[i-1][j]<=need[i][j-1]:
            strr+='R'
            j-=1        
        else:
            strr+='D'
            i-=1
    elif j==0:
        strr+='D'
        i-=1
print (i,j)
 
print(strr[::-1])

@Red white socks · 10.07.2024, 20:34

Сообщение от DenisSimahin

Вот мой код на эту тему, помогите, понять в чем моя ошибка, почему не выводит некоторые необходимые данные

В этом копаться такое себе удовольствие. Приведите нормальный тест.
При таких-то, таких-то входных данных моя программа выводит то-то, то-то, а должна это-это.

Новые блоги и статьи Все статьи Все блоги /
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Нашел на реддите интересную статью под названием «Кто-нибудь знает, где получить бесплатный компьютер или. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .

Вывести маршрут максимальной стоимости (модифицировать)

Решение