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

@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

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

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

Новые блоги и статьи Все статьи Все блоги /
Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/

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

Решение