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

@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;
}

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

Новые блоги и статьи Все статьи Все блоги /
Уведомление о неверно выбранном значении справочника 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/

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

	Задача "Вывести маршрут максимальной стоимости" 28.03.2019, 19:52. Показов 70908. Ответов 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 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 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 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,760
	21.08.2020, 16:26
	Интересно, сколько по времени будет выполнятся поиск пути на матрице 100x100... 0

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

Решение