Question

Вывести маршрут максимальной стоимости В левом верхнем углу прямоугольной таблицы размером N×M находится черепашка. В каждой клетке таблицы записано некоторое число. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы. Подсчитаем сумму чисел, записанных в клетках, через которую проползла черепашка (включая начальную и конечную клетку). Найдите наибольшее возможное значение этой суммы и маршрут, на котором достигается эта сумма.

Answer 1

Ответ:

#include <iostream>

#include <algorithm>

using namespace std;

int main()

{

int n(0),m(0);

cin >> n >> m;

int matrix[n][m];

char arr[n][m];

arr[0][0] = '0';

for(int i = 0;i<n;++i){

for(int j = 0;j<m;++j){

cin >> matrix[i][j];

if(!i && !j)continue;

if(!i){

matrix[i][j] += matrix[i][j-1];

arr[i][j] = 'R';

}

if(!j){

matrix[i][j] += matrix[i-1][j];

arr[i][j] = 'D';

}

if(i && j){

matrix[i][j] += max(matrix[i-1][j],matrix[i][j-1]);

if(max(matrix[i-1][j],matrix[i][j-1]) == matrix[i-1][j])arr[i][j] = 'D';

else arr[i][j] = 'R';

}

}

}

cout << matrix[n-1][m-1];

cout << "\n";

string s;

for(int i = n-1;;){

for(int j = m-1;;){

if(arr[i][j] == '0'){

reverse(s.begin(),s.end());

s.erase(0,1);

cout << s << endl;

return 0;

}

s.push_back(arr[i][j]);

s.push_back(' ');

if(arr[i][j] == 'R'){

j -= 1;

continue;

}

if(arr[i][j] == 'D'){

i -= 1;

continue;

}

}

}

cout << endl;

return 0;

}

Объяснение:

Answer 2

Для нахождения маршрута с максимальной стоимостью черепашки можно воспользоваться динамическим программированием. Вам нужно создать дополнительную таблицу размером N×M, в которой будет храниться сумма наибольшей стоимости, которую можно получить, дойдя до каждой клетки.

Пусть ваша исходная таблица с числами имеет размер N×M и называется input_table, а таблица для хранения сумм максимальной стоимости будет называться dp_table.

Инициализация:

1. Заполните первую строку и первый столбец dp_table так, чтобы они содержали кумулятивные суммы вдоль соответствующих строк и столбцов input_table.

Проход по таблице: 2. Для каждой клетки (i, j) dp_table[i][j] будет равно максимуму из двух значений: dp_table[i-1][j] и dp_table[i][j-1], плюс значение из input_table[i][j].

Вычисление маршрута: 3. Чтобы восстановить маршрут с максимальной стоимостью, начните с правой нижней клетки dp_table[N-1][M-1] и двигайтесь вверх и влево, выбирая путь, который привел к максимальной стоимости.

Вот Python-код, который реализует этот подход:

pythonCopy code
def find_max_cost_route(input_table):
    N = len(input_table)
    M = len(input_table[0])
    
    # Инициализация dp_table
    dp_table = [[0] * M for _ in range(N)]
    dp_table[0][0] = input_table[0][0]
    
    # Заполнение первой строк и первого столбца dp_table
    for i in range(1, N):
        dp_table[i][0] = dp_table[i-1][0] + input_table[i][0]
    for j in range(1, M):
        dp_table[0][j] = dp_table[0][j-1] + input_table[0][j]
    
    # Заполнение dp_table и нахождение максимальной стоимости
    for i in range(1, N):
        for j in range(1, M):
            dp_table[i][j] = max(dp_table[i-1][j], dp_table[i][j-1]) + input_table[i][j]
    
    # Нахождение маршрута с максимальной стоимостью
    i, j = N-1, M-1
    max_cost_route = [(i, j)]
    while i > 0 or j > 0:
        if i > 0 and j > 0:
            if dp_table[i-1][j] > dp_table[i][j-1]:
                i -= 1
            else:
                j -= 1
        elif i > 0:
            i -= 1
        else:
            j -= 1
        max_cost_route.append((i, j))
    
    # Реверсируем маршрут, чтобы начать с начальной клетки
    max_cost_route.reverse()
    
    return dp_table[N-1][M-1], max_cost_route

# Пример использования
input_table = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

max_cost, route = find_max_cost_route(input_table)
print("Максимальная стоимость:", max_cost)
print("Маршрут с максимальной стоимостью:", route)

Вызов функции find_max_cost_route(input_table) вернет максимальную стоимость и маршрут с максимальной стоимостью для данной таблицы.