如何找到矿山中最大数量的钻石？

Question

我必须编写一个程序，接受二维数组的 rows/columns 的数量以及数组本身作为输入 n。

它应该计算它可以在矿井中收集的最大 'diamonds' 数量，只需要向右、向右或向右走。

该代码没有给出任何编译错误，但是当我运行它时，它给出了一个分段错误。

可能这与我在 main 中使用的 malloc 有关，但我不知道如何解决它。

密码是：

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

#define max(a,b) (((a)>(b))?(a):(b))

int maxdiam(int *mine, int m, int n) {
    // table for storing intermediates
    int table[m][n];

    memset(table, 0, sizeof(table));

    for(int c=n-1; c>=0; c--) {
        for (int r=0; r<m; r++) {
            // right
            int right = (c == n-1)? 0: table[r][c+1];

            // right up
            int rightup = (r == 0 || c == n-1)? 0:table[r-1][c+1];
            // right down
            int rightdown = (r == m-1 || c == n-1)? 0:
                             table[r+1][c+1];

            // Max collected
            table[r][c] = mine[r] + max(right, max(rightup, rightdown));
        }
    }

    // max diam == max first column all rows
    int res = table[0][0];

    for (int i=1; i<m; i++)
        res = max(res, table[i][0]);
    return res;
}

// Driver Code
int main(int argc, char* v[]) {
    int n;

    scanf("%d", &n);

    int m = n;
    int **mine = malloc(sizeof(int *) * n);

    for(int i = 0; i < n; i++) {
        mine[i] = (int *)malloc(n * sizeof(int));
    }

    for(int i=0; i < n; i++) {
        for(int j=0; j < n; j++) {
            scanf("%d", &mine[i][j]);
        }
    }

    printf("%d\n", maxdiam(&mine[m][n], m, n));

    return 0;
}

预期的输入和输出：

input:
3
1 3 3
2 1 4
0 6 4
output:
12 

input:
4
1 3 1 5
2 2 4 1
5 0 2 3
0 6 1 2
output:
16 

input:
4
10 33 13 15
22 21 4  1
5  0  2  3
0  6  1  2
output:
83

我不是要找人为我的问题提供正确的代码，但我希望有人知道为什么我会收到上述错误以及如何解决这个问题。

Answer 1

你的代码中有很多问题，其中一些问题已经在评论中提到了。下面，我发布了一个 working 版本（我用你的示例数据对其进行了测试），在我进行更改的代码中添加了注释（所有这些都有三重斜线，/// 标记它们）。

撇开这几个问题不谈，您的代码逻辑（遍历数组寻找最大值的方式）没有问题 - 这就是为什么我将此答案作为完整解决方案发布的原因。

请随时询问更多信息and/or澄清我所做的任何更改。

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

///#define max(a,b) (((a)>(b))?(a):(b)) // Should be already defined in stdlib.h

int maxdiam(int** mine, int m, int n) { /// NOTE: "mine" is an int** - NOT an int*
    // table for storing intermediates
/// int table[m][n]; // Variable length arrays are NOT standard C, so use the following ...
    int** table = malloc(sizeof(int*) * m); // This allocates a 'm' size array of pointers ...
    for (int i = 0; i < m; ++i) {
        table[i] = malloc(sizeof(int) * n);  // ... each of which points to an 'n' size array of intregers
        memset(table[i], 0, sizeof(int) * n); // And here, we set the values to all zero.
    }
/// memset(table, 0, sizeof(table)); // This cannot be used with the 'malloc' system!
    for (int c = n - 1; c >= 0; c--) {
        for (int r = 0; r < m; r++) {
            // right
            int right = (c == n - 1) ? 0 : table[r][c + 1];
            // right up
            int rightup = (r == 0 || c == n - 1) ? 0 : table[r - 1][c + 1];
            // right down
            int rightdown = (r == m - 1 || c == n - 1) ? 0 : table[r + 1][c + 1];
            // Max collected
        /// table[r][c] = mine[r] + max(right, max(rightup, rightdown)); // You forgot the column index!
            table[r][c] = mine[r][c] + max(right, max(rightup, rightdown));
        }
    }
    // max diam == max first column all rows
    int res = table[0][0];
    for (int i = 1; i < m; i++) res = max(res, table[i][0]);

    /// Here, we free the 'temporary' array(s) we created ...
    for (int i = 0; i < m; ++i) free(table[i]);
    free(table);

    return res;
}

// Driver Code
int main(int argc, char* v[]) {
    int n;

    scanf("%d", &n);
    int m = n;
    int** mine = malloc(sizeof(int*) * n);

    for (int i = 0; i < n; i++) {
        mine[i] = malloc(n * sizeof(int)); // Note: you shouldn't "cast" the return value of malloc!
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &mine[i][j]);
        }
    }
/// printf("%d\n", maxdiam(&mine[m][n], m, n)); // This will pass the address of the first element of the last row!
    printf("%d\n", maxdiam(mine, m, n));        // Use this instead - to pass the address of the 'row' array!
    return 0;
}

注意：关于 "variable length arrays" 我已经标记的位 - 如果您的系统（可能 gcc）允许这样做，那么您可以继续使用它，因此取出我用malloc和free给出的系统。但是，我认为这不是学习 C 编程的最佳方法。

如何找到矿山中最大数量的钻石？

How to find the maximum amount of diamonds in a mine?

c

arrays

2d