Question

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

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

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

Давайте рассмотрим код на C++, который решает данную задачу:

cppCopy code
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, M; // Размеры таблицы
    cin >> N >> M;

    vector<vector<int>> table(N, vector<int>(M)); // Массив для хранения чисел в клетках
    vector<vector<int>> dp(N, vector<int>(M));    // Массив для хранения максимальных сумм

    // Ввод чисел в таблицу
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> table[i][j];
        }
    }

    // Инициализация первой клетки
    dp[0][0] = table[0][0];

    // Инициализация первой строки и первого столбца
    for (int i = 1; i < N; i++) {
        dp[i][0] = dp[i - 1][0] + table[i][0];
    }
    for (int j = 1; j < M; j++) {
        dp[0][j] = dp[0][j - 1] + table[0][j];
    }

    // Заполнение массива dp
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < M; j++) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + table[i][j];
        }
    }

    // Максимальная сумма будет храниться в dp[N-1][M-1]
    cout << "Максимальная сумма: " << dp[N - 1][M - 1] << endl;

    // Восстановление маршрута
    int i = N - 1, j = M - 1;
    vector<pair<int, int>> path;
    path.push_back(make_pair(i, j));

    while (i > 0 || j > 0) {
        if (i > 0 && dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
        path.push_back(make_pair(i, j));
    }

    // Вывод маршрута
    cout << "Маршрут:" << endl;
    for (int k = path.size() - 1; k >= 0; k--) {
        cout << "(" << path[k].first << ", " << path[k].second << ")" << endl;
    }

    return 0;
}

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