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

@Limons · Регистрация: 22.03.2019

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

Здравствуйте, помогите пожалуйста с решением задачи

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

@Starfer · 28.03.2019, 20:23

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
global n,m,matrix
 
def rec(sum = 0, path = [], posx = 0, posy = 0):
    sum += matrix[posx][posy]
    if posx == n - 1 and posy == m - 1:
        return (sum,path)
    vars = []
    if posx != n - 1:
        newpath = path.copy()
        newpath.append('D')
        vars.append(rec(sum,newpath,posx + 1,posy))
    if posy != m - 1:
        newpath = path.copy()
        newpath.append('R')
        vars.append(rec(sum,newpath,posx,posy + 1))
    return max(vars,key = lambda x: x[0])
 
n,m = [int(i) for i in input().split()]
matrix = [[int(i) for i in input().split()] for j in range(n)]
res = rec()
print(res[0])
print(' '.join(res[1]))

Алгоритм очень неэффективный, но работает

@Limons · 28.03.2019, 20:41 **[ТС]**

Спасибо большое, программа проходит 16 тестов из 17, в 17 превышение времени

@dondublon · 29.03.2019, 11:11

Starfer, Limons, потому что без кеширования.
См, клетки:
1 2 ...
3 4 ...
...
В клетку 4 черепаха может попасть двумя путями - через клетки 2 и 3. И путь из 4 будет вычисляться заново для каждого варианта. Если мы рассмотрим клетку подальше от начала, там число путей, а следовательно, и повторов, будет расти астрономически (полагаю, как n!).

Это задачка на динамическое программирование, простая, но тем не менее, почитать стоит.

@Starfer · 29.03.2019, 20:43

dondublon, Limons, написал новый код, используя динамическое программирование. Полагаю, что теперь программа будет выполняться за линейное время (O(n)):

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
30
31
32
global n,m,matrix,pathmatrix
 
#Возвращает минимальный путь от (0,0) до (x,y)
def rec(x, y):
    try:
        return pathmatrix[x,y]
    except:
        if x > 0:
            left = rec(x - 1, y)
        else:
            left = (-1,[])
        if y > 0:
            up = rec(x, y - 1)
        else:
            up = (-1,[])
        maxdist = max(left[0], up[0]) + matrix[x][y]
        if left[0] > up[0]:
            path = pathmatrix[x - 1,y][1].copy()
            path.append('D')
        else:
            path = pathmatrix[x,y - 1][1].copy()
            path.append('R')
        pathmatrix[x,y] = (maxdist,path)
        return pathmatrix[x,y]
 
n,m = [int(i) for i in input().split()]
matrix = [[int(i) for i in input().split()] for j in range(n)]
#Тут будем хранить минимальную дистанцию и путь до каждой клетки от (0,0)
pathmatrix = {(0,0) : (matrix[0][0], [])}
res = rec(n-1,m-1)
print(res[0])
print(' '.join(res[1]))

@Krushiler · 08.07.2019, 11:12

можешь, пожалуйста, на C++ или Java это написать?

@Donsemon · 21.08.2020, 15:16

На Сириусе выдается ошибка:
Программа выполнялась слишком долго и была прервана

@Fudthhh · 21.08.2020, 16:03

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
def task(n: int, m: int, matrix: [[int, ...], ...]) -> (int, str):
    if n > 1:
        if m > 1:
            (dv, dp), (rv, rp) = task(n - 1, m, matrix), task(n, m - 1, matrix)
        else:
            (dv, dp), (rv, rp) = task(n - 1, m, matrix), (0, "")
    else:
        return matrix[-n][-m] + 0, ""
 
    if dv > rv:
        return matrix[-n][-m] + dv, "D" + dp
    else:
        return matrix[-n][-m] + rv, "R" + rp
 
 
print(task(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, 'DDRRRRDD')

@u235 · 21.08.2020, 16:26

Интересно, сколько по времени будет выполнятся поиск пути на матрице 100x100...

@bogdn · 02.12.2021, 21:27

17/17 тестов. макс время 0.036

Python
1
2
3
4
5
6
7
8
9
10
11
12
n,m = map(int, input().split())
arr = [[] for i in range(n)]
 
for i in range(n): arr[i] = list(map(int, input().split()))
 
for i in range(n):
    for j in range(m):
        if(i-1>-1 and j-1>-1): arr[i][j] += max(arr[i-1][j],arr[i][j-1])
        elif(i-1>-1): arr[i][j] += arr[i-1][j]
        elif(j-1>-1): arr[i][j] += arr[i][j-1]
 
print(arr[n-1][m-1])

Добавлено через 21 минуту
забыл добавить вывод строки

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
i,j = n-1,m-1
res = []
while(i != 0 or j != 0):
    if(i>0 and j>0) :
        if(arr[i-1][j]>arr[i][j-1]):
            res.append('D')
            i-=1
        else:   
            res.append('R')
            j-=1
    elif(i>0):
        res.append('D')
        i-=1
    elif(j>0):
        j-=1 
        res.append('R')
res.reverse()
print(arr[n-1][m-1])
for i in range(len(res)): print(res[i],end='')

@willow_33 · 31.01.2022, 13:52

Подскажите, не принимает мою работу, пишет ошибку "Программа выводит ответ в неверном формате".

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
N, M = map(int, input().split())
w=[list(map(int,input().split()))for i in range(N)]
a=[[0]*(M+1) for i in range (N+1)]
b=[]
a[1][1]=w[0][0]
for i in range (1,N+1):
    a[i][1]=w[i-1][0]+a[i-1][1]
for j in range (1,M+1):
    a[1][j]=w[0][j-1]+a[1][j-1]
for i in range (1,N+1):
    for j in range (1,M+1):
        a[i][j]=w[i-1][j-1]+max(a[i-1][j],a[i][j-1])
i,j=N,M
while i>=1 and j>=1:
    if a[i-1][j]>a[i][j-1]:
        b.append('D')
        i-=1
    else:
        b.append('R')
        j-=1
print(a[-1][-1])
print(' '.join(b[-2::-1]))

Для
[[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

@Shipuchka_47 · 15.06.2022, 22:29

Молчу по поводу нормальности такого решения, но вроде понятно что за чем идёт и в Сириусе прошло, если появятся критики по решению, то знайте что мне абсолютно всё равно на ваши эмоции и слова!

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())
arr, ans_lst =[list(map(int,input().split())) for i in range(n)], []
count1, count2 = 0, 0
for i in range(n):
    for j in range(m):
        if i >= 1 and j >= 0: count1 = arr[i - 1][j]
        if i >= 0 and j >= 1: count2 = arr[i][j - 1]
        arr[i][j] += max(count1, count2)
        count1, count2 = 0, 0
i, j = n - 1, m - 1
while i != 0 or j != 0:
    if j >= 1 and i >= 1:
        if arr[i][j - 1] > arr[i - 1][j]:ans_lst.append("R")
        else:ans_lst.append("D")
    else:
        if j >= 1:ans_lst.append("R")
        else:ans_lst.append("D")
    if ans_lst[-1] == "D":i -= 1
    else:j -= 1
print(arr[-1][-1])    
print(*(ans_lst[::-1]))

Добавлено через 23 минуты
willow_33,

Для своего кода вверху относительно таблички для ввода текста в ответе на этом форуме есть кнопка python, нажми на неё и между двумя появившимися штуками вставь код, а то пробелы где вообще не ясно

@Nedodik · 05.11.2025, 22:11

C++
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <vector>
 
using namespace std;
 
int main(){
    int n, m, k;
    cin >> n >> m;
    vector <vector <int> > T(n+1, vector <int> (m+1, 0));
    for (int i = 1; i < T.size(); i++){
        for (int j = 1; j < T[i].size(); j++){
            cin >> k;
            T[i][j] = k;
        }
    }
 
    for (int i = 1; i < T.size(); i++){
        for (int j = 1; j < T[i].size(); j++){
            T[i][j] += max(T[i][j-1], T[i-1][j]);
        }
    }
    for (int i = 0; i < T.size(); i++){
        T[i][0] = -1;
    }
    for (int j = 0; j < T[0].size(); j++){
        T[0][j] = -1;
    }
    cout << T[n][m] << endl;
 
    vector <int> S;
    int i = n, j = m;
    while ((i != 1) || (j != 1)){
        if (T[i-1][j] > T[i][j-1]){
            i--;
            S.push_back(1); //Down
        }else{
            j--;
            S.push_back(-1); //Right
        }
    }
 
    for(int i = S.size()-1; i >= 0; i--){
        if (S[i] == 1){
            cout << "D ";
        }else{
            cout << "R ";
        }
    }
    cout << endl;
 
    return 0;
}

Вроде рабочее решения

Новые блоги и статьи Все статьи Все блоги /
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 - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Limons 0 / 0 / 0 Регистрация: 22.03.2019 Сообщений: 6

	Задача "Вывести маршрут максимальной стоимости" 28.03.2019, 19:52. Показов 69987. Ответов 12 Метки нет (Все метки) Здравствуйте, помогите пожалуйста с решением задачи В левом верхнем углу прямоугольной таблицы размером 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 0

@Limons 0 / 0 / 0 Регистрация: 22.03.2019 Сообщений: 6
	28.03.2019, 20:41 [ТС]
	Спасибо большое, программа проходит 16 тестов из 17, в 17 превышение времени 0

@dondublon 4648 / 2068 / 366 Регистрация: 17.03.2012 Сообщений: 10,168 Записей в блоге: 6
	29.03.2019, 11:11
	Starfer, Limons, потому что без кеширования. См, клетки: 1 2 ... 3 4 ... ... В клетку 4 черепаха может попасть двумя путями - через клетки 2 и 3. И путь из 4 будет вычисляться заново для каждого варианта. Если мы рассмотрим клетку подальше от начала, там число путей, а следовательно, и повторов, будет расти астрономически (полагаю, как n!). Это задачка на динамическое программирование, простая, но тем не менее, почитать стоит. 2

@Krushiler 2 / 2 / 0 Регистрация: 16.02.2017 Сообщений: 4
	08.07.2019, 11:12
	можешь, пожалуйста, на C++ или Java это написать? 0

@Donsemon 0 / 0 / 0 Регистрация: 17.04.2020 Сообщений: 3
	21.08.2020, 15:16
	На Сириусе выдается ошибка: Программа выполнялась слишком долго и была прервана 0

@u235 5514 / 2867 / 571 Регистрация: 07.11.2019 Сообщений: 4,751
	21.08.2020, 16:26
	Интересно, сколько по времени будет выполнятся поиск пути на матрице 100x100... 0

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

Решение