View difference between Paste ID: qSfeicx5 and 3pYJFD2n
SHOW: | | - or go back to the newest paste.
1
// prototipovi stack funkcija
2
3
stack_t stack_new();
4
void stack_delete(stack_t stack);
5
void stack_push(stack_t stack, stack_element_t elem);
6
stack_element_t stack_pop(stack_t stack);
7
stack_element_t stack_top(stack_t stack);
8
int stack_is_empty(stack_t stack);
9
10
// rekurzivno traži najjeftiniji spust kroz matricu, korisnik daje indeks ćelije od koje se kreće
11
12
void traverseOpti(struct path **matrix, unsigned row, unsigned col, int path_cost, int *min_cost, int *cnt, stack_t answer, FILE *f)
13
{
14
    stack_t temp = NULL;
15
    char buffer[16];
16
    path_cost += matrix[row][col].value;
17
    matrix[row][col].sum = path_cost;
18
    (*cnt)++; // brojanje poziva
19
    temp = stack_new();
20
    fprintf(f, "Broj poziva: %d, min_cost: %s, path_cost: %d, value: %d, sum: %d\n", *cnt, *min_cost == INT_MAX ? "Inf" : itoa(*min_cost, buffer, 10), path_cost, matrix[row][col].value, matrix[row][col].sum); // logiranje
21
    if(matrix[row][col].sum > *min_cost) // ako smo tu već bili prije s manjim utroškom ni ne idi u tu granu
22
    {
23
        stack_delete(temp);
24
        return;
25
    }
26
    if(row == MATRIX_ROW - 1) // ako smo na dnu matrice
27
    {
28
        if(path_cost < *min_cost) // ako smo pronašli novu optimalnu putanju
29
        {
30
            *min_cost = path_cost;
31
            stack_delete(answer);
32
            answer = stack_new();
33
            while(!stack_is_empty(temp))
34
                stack_push(answer, stack_pop(temp));   
35
        }
36
        stack_delete(temp);
37
        return;
38
    }
39
    if (col < MATRIX_COL - 1) // idi dolje desno
40
    {
41
        stack_push(temp, matrix[row + 1][col + 1].value);
42
        traverse(matrix, row + 1, col + 1, path_cost, min_cost, cnt, answer, f);
43
        stack_pop(temp);
44
    }
45
  // idi ravno dolje
46
47-
  stack_push(temp, matrix[row + 1][col].value);
47+
    stack_push(temp, matrix[row + 1][col].value);
48
    traverse(matrix, row + 1, col, path_cost, min_cost, cnt, answer, f);
49
    stack_pop(temp);
50
51
    if (col > 0) // idi dolje lijevo
52
    {
53
        stack_push(temp, matrix[row + 1][col - 1].value);
54
        traverse(matrix, row + 1, col - 1, path_cost, min_cost, cnt, answer, f);
55
        stack_pop(temp);
56
    }
57
    stack_delete(temp);
58
}