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

@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

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

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .

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

Решение