编辑代码

#include <iostream>
#include <vector>
#include <algorithm>  // Add this line to include the <algorithm> header

using namespace std;

// 计算机器人获得硬币的最大值
int maxCoins(vector<vector<int> >& grid, vector<pair<int, int> >& path) {
    int rows = grid.size();
    if (rows == 0) return 0;
    int cols = grid[0].size();
    // 初始化动态规划表
    vector<vector<int> > dp(rows, vector<int>(cols, 0));
    // 填充动态规划表
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (i == 0 && j == 0) {
                dp[i][j] = grid[i][j];
            } else if (i == 0) {
                dp[i][j] = dp[i][j - 1] + grid[i][j];
            } else if (j == 0) {
                dp[i][j] = dp[i - 1][j] + grid[i][j];
            } else {
                dp[i][j] = grid[i][j] + max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    // 回溯找到机器人的路径
    int i = 0;
    int j = 0;
    path.push_back(make_pair(i, j));

    while (i < rows - 1 || j < cols - 1) {
        if (i == rows - 1) {
            ++j;
        } else if (j == cols - 1) {
            ++i;
        } else {
            if (dp[i + 1][j] > dp[i][j + 1]) {
                ++i;
            } else {
                ++j;
            }
        }
        path.push_back(make_pair(i, j));
    }
    // 使用reverse进行反转
    reverse(path.begin(), path.end());

    return dp[rows - 1][cols - 1];
}

int main() {
    // 初始化二维数组表示硬币数
    int arr[][6] = {
        {0, 0, 0, 0, 1, 0},
        {0, 1, 0, 1, 0, 0},
        {0, 0, 0, 1, 0, 1},
        {0, 0, 1, 0, 0, 1},
        {1, 0, 0, 0, 1, 0}
    };
    
    vector<vector<int> > grid;
    for (int i = 0; i < 5; ++i) {
        vector<int> row(arr[i], arr[i] + 6);
        grid.push_back(row);
    }

    // 存储机器人的路径
    vector<pair<int, int> > path;

    // 调用函数计算最大硬币数并获取路径
    int maxCoinsValue = maxCoins(grid, path);

    // 输出结果
    cout << "机器人能够获得的最大硬币数为：" << maxCoinsValue << endl;
    cout << "机器人的路径为：" << endl;
    for (size_t i = 0; i < path.size(); ++i) {
        cout << "(" << path[i].first << "," << path[i].second << ")";
        if (i < path.size() - 1) {
            cout << " -> ";
        }
    }
    cout << endl;

    return 0;
}