编辑代码

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

#define MAX_ROWS 100
#define MAX_COLS 100

// 计算两个数中的较大值
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 找到机器人能够找到的最大硬币数及路径
void findMaxCoins(int board[MAX_ROWS][MAX_COLS], int rows, int cols) {
    int dp[MAX_ROWS][MAX_COLS];

    // 初始化第一行和第一列
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            dp[i][j] = 0;
        }
    }

    // 动态规划，计算最大硬币数
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (i == 0 && j == 0) {
                dp[i][j] = board[i][j];
            } else if (i == 0) {
                dp[i][j] = dp[i][j - 1] + board[i][j];
            } else if (j == 0) {
                dp[i][j] = dp[i - 1][j] + board[i][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + board[i][j];
            }
        }
    }

    // 输出最大硬币数
    printf("最大硬币数: %d\n", dp[rows - 1][cols - 1]);

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

int main() {
    int rows, cols;
    printf("请输入木板的行数和列数: ");
    scanf("%d %d", &rows, &cols);

    int board[MAX_ROWS][MAX_COLS];

    printf("请输入每个格子上的硬币数（逐行输入）:\n");
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            scanf("%d", &board[i][j]);
        }
    }

    findMaxCoins(board, rows, cols);

    return 0;
}