编辑代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int collectCoin(vector<vector<int>>& coin, vector<pair<int, int>>& path) {
    // 1. 构建动态规划表格
    int rowCount = coin.size() + 1;
    int colCount = coin[0].size() + 1;
    vector<vector<int>> dpArray(rowCount, vector<int>(colCount, 0));

    // 2. 填充动态规划表格
    for (int i = 1; i < rowCount; ++i) {
        for (int j = 1; j < colCount; ++j) {
            dpArray[i][j] = max(dpArray[i-1][j], dpArray[i][j-1]) + coin[i-1][j-1];
        }
    }

    // 3. 找到收集路径
    int i = rowCount - 1;
    int j = colCount - 1;

    while (i > 0 && j > 0) {
        path.emplace_back(i, j);

        if (dpArray[i-1][j] > dpArray[i][j-1]) {
            i = i - 1;
        } else {
            j = j - 1;
        }
    }

    path.emplace_back(1, 1);

    reverse(path.begin(), path.end()); // 反转路径，使其按顺序存储

    return dpArray[rowCount-1][colCount - 1];
}

void printPath(const vector<pair<int, int>>& path) {
    for (const auto& p : path) {
        cout << "(" << p.first << "," << p.second << ")" << endl;
    }
}

int main() {
    vector<vector<int>> coin = {
        {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<pair<int, int>> path;
    cout << "收集到的硬币数：" << collectCoin(coin, path) << endl;
    printPath(path);

    return 0;
}