8.5 Corrigés des exercices
}
}
}
x = (rand ()
y = (rand ()
map [ x ] [ y ] = 1 ;
(RAND_MAX + 1.0)) * width ;
(RAND_MAX + 1.0)) * height ;
in t g [ MaxEdge ] [ MaxEdge ] ;
list stackAt [MaxEdge * MaxEdge ];
int nodes = O ;
int dijkstra (Point start , Point goal ) {
for ( int i = O ; i < height ; i++)
for (int j = O ; j < width ; j++)
g [i] [j ) = -1;
for ( int i = O ; i < height * width ; i++)
stackAt [i]. clear ();
nodes = 1;
int currentg = O ;
Point current = start ;
g [start .x] [start .y] = O ;
while ( current ! = goal ) {
nodes ++;
Point p [4] ;
p [0] . set (current .x + l, current .y);
p [l]. set (current .x - 1, current .y);
p [2]. set ( current . x, current . y + 1);
p [3]. set (current .x, current .y - l);
fo r (int i = O ; i < 4; i++)
if ((p [i ].x >= 0) && (p [i ].x < width ) &&
( p [ i ] . y >= 0 ) && ( p [ i ] . y < h e i g h t ) )
if ( map [ p [ i ] . x] [ p [ i ] . y] -- 0) {
i f ( g ( p ( i ) . X ) ( p ( i ) . y ) == - 1 ) {
g [p [i].x] [p [i].y] = currentg + 1;
stackAt [currentg + l].push_back (p [i));
}
163
else if (g [p [i].x] [p [i].y] > currentg + 1) {
g [p [i].x] [p [i].y] = currentg + 1;
stackAt [currentg + 1].push_back (p [i]);
fprintf (stderr , "+" );
}
}