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