Помогите решить Вывести маршрут максимальной стоимости В левом верхнем углу прямоугольной таблицы размером N×M находится черепашка. В каждой клетке таблицы записано некоторое число. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.
Подсчитаем сумму чисел, записанных в клетках, через которую проползла черепашка (включая начальную и конечную клетку). Найдите наибольшее возможное значение этой суммы и маршрут, на котором достигается эта сумма.
Входные данные
В первой строке входных данных записаны два натуральных числа N и M, не превосходящих 100 — размеры таблицы. Далее идут N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100.
Выходные данные
Первая строка выходных данных содержит максимальную возможную сумму, вторая — маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N−1 букву D, означающую передвижение вниз и M−1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них. Мое решение вот. Но вывод не знаю как правильно организовать. У меня не так как нужно
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int gcd(int a, int b) { return __gcd(a, b); }
int lcm(int a, int b) { return abs(a * b) / gcd(a, b); }
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout.precision(9);
cout << fixed;
int n;
int m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (auto& i : a) {
for (auto& j : i) {
char c;
cin >> c;
j = c - '0';
}
}
vector<vector<int>> dp(n, vector<int>(m));
dp[0][0] = a[0][0];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (i == 0 && j == 0)
continue;
if (i == 0) {
dp[i][j] = a[i][j] + dp[i][j - 1];
} else if (j == 0) {
dp[i][j] = a[i][j] + dp[i - 1][j];
} else {
dp[i][j] = a[i][j] + max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
vector<vector<char>> ans(n, vector<char>(m, '-'));
vector<int> dx = {0, -1};
vector<int> dy = {-1, 0};
int x = n - 1;
int y = n - 1;
ans[x][y] = '#';
while (x != 0 || y != 0) {
int max_one = numeric_limits<int>::min();
int max_i = 0;
int max_j = 0;
for (size_t d = 0; d < dx.size(); ++d) {
int i = x + dx[d];
int j = y + dy[d];
bool ok = i >= 0 && j >= 0 && i < n && j < n;
if (ok && max_one < dp[i][j]) {
max_one = dp[i][j];
max_i = i;
max_j = j;
}
}
ans[max_i][max_j] = '#';
x = max_i;
y = max_j;
}
cout << dp[n - 1][m - 1] << '\n';
ans[0][0] = '#';
for (const auto& i : ans) {
copy(i.cbegin(), i.cend(), ostream_iterator<char>(cout, ""));
cout << '\n';
}
}