-
Notifications
You must be signed in to change notification settings - Fork 0
/
solver.c
116 lines (93 loc) · 3.41 KB
/
solver.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include "solver.h"
#include <stdio.h>
/* znajdowanie komórki, do której koszt dojścia jest najmniejszy */
cell* min_cost( maze* m ) {
cell *c = NULL;
double vl = 1000;
for ( int i = 0; i < m->m_size; ++i )
for ( int j = 0; j < m->m_size; ++j )
if ( m->m[i][j].visited == 0 && m->m[i][j].total_value < vl ) {
c = &m->m[i][j];
vl = c->total_value;
}
return c;
}
/* znajdowanie najkrótszej ścieżki - dijsktra */
void shortest_path( maze* m ) {
/* reset wszystkich wizytacji */
for ( int i = 0; i < m->m_size; ++i ) {
for ( int j = 0; j < m->m_size; ++j ) {
m->m[i][j].visited = 0;
}
}
/* jest to startowy wierzchołek */
m->m[0][m->start].total_value = 0;
cell* current_cell = min_cost( m );
while ( current_cell != NULL ) {
current_cell->visited = 1;
/* sprawdzam czy nie doszłam już do wierzchołka końcowego */
if ( current_cell->y == m->m_size - 1 && current_cell->x == m->finish ) {
printf("\nSCIEZKA NAJKROTSZEJ SCIEZKI, wspolrzede wierzcholkow na macierzy (od konca):\n");
cell* cc = current_cell;
cc->bounds[2] = 2;
/* wyświetlenie drogi ( przy okazji zmiany wizualne na macierzy labiryntu aby jakoś ładnie 'pokazać' tę drogę )*/
while ( cc != NULL ) {
cc->label = 'o';
printf("(%i, %i) ", cc->y, cc->x );
if ( cc->previous != NULL ) {
for( int i = 0; i < 4; ++i ) {
if ( cc->near[i] == cc->previous )
cc->bounds[i] = 2;
if ( cc == cc->previous->near[i] )
cc->previous->bounds[i] = 2;
}
} else
cc->bounds[0] = 2;
cc = cc->previous;
}
printf("\nNajmniejsza suma wag: %f\n\n", current_cell->total_value );
break;
}
/* najmniejsze koszty dojścia dla somsiadów */
double new_cost = current_cell->total_value + current_cell->value;
for( int i = 0; i < 4; ++i ) {
if ( current_cell->bounds[i] == 0 && current_cell->near[i] != NULL
&& current_cell->near[i]->total_value > new_cost ) {
current_cell->near[i]->total_value = new_cost;
current_cell->near[i]->previous = current_cell;
}
}
current_cell = min_cost( m );
}
}
/* losowe usuwanie ścianek */
void passage( cell* previous_popped, cell* popped ) {
popped->visited = 1;
if ( previous_popped != NULL ) {
// nad
if ( previous_popped->y < popped->y ) {
previous_popped->bounds[2] = 0;
popped->bounds[0] = 0;
}
// pod
if ( previous_popped->y > popped->y ) {
previous_popped->bounds[0] = 0;
popped->bounds[2] = 0;
}
// z prawo
if ( previous_popped->x < popped->x ) {
previous_popped->bounds[1] = 0;
popped->bounds[3] = 0;
}
// z lewo
if ( previous_popped->x > popped->x ) {
previous_popped->bounds[3] = 0;
popped->bounds[1] = 0;
}
}
cell* next = leave( popped );
while ( next != NULL ) {
passage( popped, next );
next = leave( popped );
}
}