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

Question

Задача из Сириус курсов:

Вывести маршрут максимальной стоимости.

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

Подсчитаем сумму чисел, записанных в клетках, через которую проползла черепашка (включая начальную и конечную клетку).

Найдите наибольшее возможное значение этой суммы и маршрут, на котором достигается эта сумма.

Входные данные

В первой строке входных данных записаны два натуральных числа N и M, не превосходящие 100 — размеры таблицы. Далее идут N строк, каждая из которых содержит M чисел, разделённых пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100.

Выходные данные

Первая строка выходных данных содержит максимальную возможную сумму, вторая — маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N−1 букву D, означающую передвижение вниз, и M−1 букву R, означающую передвижение вправо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.

Примеры:

Ввод:

Вывод:

74

D D R R R R D D

Вот моё решение, которое проходит 16 тестов из 17. Самая первая строка и столбец пустые, чтобы сделать всё одним циклом и формулой. В чём может быть ошибка?

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;

    vector<vector<int>> vv(n+1, vector<int> (m+1, 0));
    vector<string> s;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> vv[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            vv[i][j] = max(vv[i-1][j], vv[i][j-1]) + vv[i][j];
        }
    }

    int y = n,x = m;

    while(!(x==1 && y==1)) {
        if(vv[y-1][x]>vv[y][x-1]) {
            s.push_back("D");
            y--;
        }
        else {
            s.push_back("R");
            x--;
        }
    }

    cout << vv[n][m] << endl;
    for (int i = s.size()-1; i >=0; i--) {
        cout << s[i] << " ";
    }

    return 0;
}

Answer 1

В общем, 3 ошибки:

Неправильно инициализируешь массив - используешь vv[n+1][m+1], из-за чего индексы могут быть неправильными;
Необрабатываешь границы при вычислении максимальной суммы;
Неправильно определяешь направление движения: тебе ведь нужно двигаться вниз или вправо, основываясь на значениях в массиве.

Исправил код — пробуй:

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> vv(n, vector<int>(m, 0));
    

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> vv[i][j];
        }
    }

    vector<vector<int>> dp(n, vector<int>(m, 0));
    dp[0][0] = vv[0][0];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i > 0) {
                dp[i][j] = max(dp[i][j], dp[i-1][j] + vv[i][j]);
            }
            if (j > 0) {
                dp[i][j] = max(dp[i][j], dp[i][j-1] + vv[i][j]);
            }
        }
    }
    string path;
    int y = n - 1, x = m - 1;

    while (y > 0 || x > 0) {
        if (y > 0 && dp[y][x] == dp[y-1][x] + vv[y][x]) {
            path += 'D'; 
            y--;
        } else {
            path += 'R'; 
            x--;
        }
    }
    reverse(path.begin(), path.end());


    cout << dp[n-1][m-1] << endl; 
    cout << path << endl; 
    return 0;
}

БЛОГ НА HUSL

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

Ответы (1 шт):