编辑代码

#include <stdio.h>
#include <stdlib.h>

#define MAX_ROWS 100
#define MAX_COLS 100

// 定义木板上每个单元格的硬币数量
int board[MAX_ROWS][MAX_COLS] = {
    {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},
};

// 定义动态规划数组，存储到达每个单元格的最大硬币数
int dp[MAX_ROWS][MAX_COLS];

// 定义保存路径的数组
int path[MAX_ROWS][MAX_COLS];

// 计算机器人能够收集到的最大硬币数以及路径
int maxCoins(int rows, int cols) {
    // 初始化动态规划数组和路径数组
    dp[0][0] = board[0][0];
    path[0][0] = -1; // 表示起点没有前驱

    // 初始化第一行和第一列
    for (int i = 1; i < rows; i++) {
        dp[i][0] = dp[i - 1][0] + board[i][0];
        path[i][0] = 0; // 表示从上方过来
    }
    for (int j = 1; j < cols; j++) {
        dp[0][j] = dp[0][j - 1] + board[0][j];
        path[0][j] = 1; // 表示从左侧过来
    }

    // 使用动态规划填充dp数组和path数组
    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            if (dp[i - 1][j] > dp[i][j - 1]) {
                dp[i][j] = dp[i - 1][j] + board[i][j];
                path[i][j] = 0; // 表示从上方过来
            } else {
                dp[i][j] = dp[i][j - 1] + board[i][j];
                path[i][j] = 1; // 表示从左侧过来
            }
        }
    }

    // 输出路径
    int i = rows - 1;
    int j = cols - 1;
    printf("路径: (%d, %d) ", i, j);
    while (path[i][j] != -1) {
        if (path[i][j] == 0) {
            i--;
        } else {
            j--;
        }
        printf("-> (%d, %d) ", i, j);
    }
    printf("\n");

    // 返回最大硬币数
    return dp[rows - 1][cols - 1];
}

int main() {
    int rows = 5; // 木板的行数
    int cols = 6; // 木板的列数
    // 计算最大硬币数并输出路径
    int result = maxCoins(rows, cols);
    // 输出最大硬币数
    printf("硬币数: %d\n", result);

    result = maxCoins(5, 5);
    // 输出最大硬币数
    printf("硬币数: %d\n", result);

    result = maxCoins(4, 4);
    // 输出最大硬币数
    printf("硬币数: %d\n", result);

    return 0;
}