0

Помогите решить Вывести маршрут максимальной стоимости В левом верхнем углу прямоугольной таблицы размером 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';
  }
}
2
  • Выложите попытки решить задачу, даже если они неудачные, мы поможем до вести их до финала. А без них ваш вопрос просто закроют. 22 мар 2021 в 15:36
  • Я с выводом чет как-то не могу. 22 мар 2021 в 15:46

1 ответ 1

1

Вот в том месте, где заполняете ячейку dp[][], записывайте направление в дополнительную матрицу такого же размера.

Вместо max(dp[i][j - 1], dp[i - 1][j]); используйте свой выбор максимума, чтобы знать направление прихода в ячейку.

По окончанию заполнения таблиц размотайте путь из последней ячейки в обратном направлении

(а если начать решение ДП из последней ячейки, то путь из первой сразу в нужном направлении получится)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.