Как найти максимальное количество алмазов в шахте?

Question

Я должен сделать программу, которая принимает в качестве входных данных n количество строк / столбцов для двумерного массива и сам массив.

Он должен рассчитывать максимальное количество «алмазов», которое он может собрать вшахта, только двигаясь направо, прямо вверх или вниз.

Код не дает никакой ошибки компиляции, но когда я его запускаю, он дает ошибку сегментации.

Возможно, это как-то связано с malloc, который я использую в своем main, но я не знаю, как это исправить.

Код:

#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

В вашем коде есть ряд проблем, некоторые из которых уже упоминались в комментариях. Ниже я опубликовал рабочую версию (я протестировал ее с вашими примерами данных), с комментариями в коде, где я внес изменения (все из которых имеют тройной слеш, /// для отметкиих).

Эти несколько проблем в стороне, логика вашего кода (как вы пересекаете массив, ища максимум) в порядке - вот почему я опубликовал этот ответ как полное решение.

Пожалуйста, не стесняйтесь спрашивать дополнительную информацию и / или разъяснения о любых внесенных мною изменениях.

#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;
}

ПРИМЕЧАНИЕ. На бите, который я пометил о массивах переменной длины«- Если ваша система (вероятно, gcc) позволяет это, то вы можете продолжать использовать это, и, таким образом, удалить систему, которую я дал, используя malloc и free. Однако я не думаю, что это лучший способ научиться программированию C.