0 1 2 3 0123456789012345678901234567890123456 0 #################################E### 1 ###....#.....#......###...#...#...#.# 2 #...##...###...####.....#..##.#.##..# 3 #.#########.###....##.####.##.#.#..## 4 #.............##.######..#......#...# 5 #####.#####.#..........#.##########.# 6 #S..........###.#.#.##..............# 7 #####################################
Since the graph is already implicitly given by the character matrix of the maze, the only additional data structure we need is a color matrix:
int color[num_rows][num_columns];
white
= an undiscovered vertex (not yet in the queue)
gray
= a vertex currently in the queue
black
= a finished vertex (not in the queue anymore)
for row from 0 to num_rows-1 { for column from 0 to num_columns-1 { color[row][column] = white; } }We initialize the queue with the start field.
q = new queue(); q.enqueue(start_row,start_column); color[start_row][start_column] = gray;Now -- while the queue is not empty -- we run the loop of the breadth-first search.
while (q.head != q.tail) { v = q.dequeue(); color[v.row][v.column] = black; for each (r,c) adjacent to (row,column) { if (maze[r][c]!='#' && color[r][c]==white) { q.enqueue(r,c); color[r][c] = gray; } } }After the loop has finished, all nodes reachable from the start are black. The unreachable nodes are still white.
switch (color[exit_row][exit_column]) { case white: print("Exit is unreachable"); break; case black: print("Exit is reachable"); break; }
int distance[num_rows][cum_columns];
for row from 0 to num_rows-1 { for column from 0 to num_columns-1 { color[row][column] = white; distance[row][column] = MAXINT; } } q = new queue(); q.enqueue(start_row,start_column); color[start_row][start_column] = gray; distance[start_row][start_column] = 0; while (q.head != q.tail) { v = q.dequeue(); color[v.row][v.column] = black; for each (r,c) adjacent to (row,column) { if (maze[r][c]!='#' && color[r][c]==white) { q.enqueue(r,c); color[r][c] = gray; distance[r][c] = distance[row][column] + 1; } } } switch (color[exit_row][exit_column]) { case white: print("Exit is unreachable."); break; case black: print("Exit is reachable in "+distance[exit_row][exit_column+" steps"); break; }
vertex pred[num_rows][num_columns];The start node has no predecessor. For all other nodes, the predecessor is set when the node is enqueued.
for row from 0 to num_rows-1 { for column from 0 to num_columns-1 { color[row][column] = white; distance[row][column] = MAXINT; } } q = new queue(); q.enqueue(start_row,start_column); color[start_row][start_column] = gray; distance[start_row][start_column] = 0; pred[start_row][start_column] = null; while (q.head != q.tail) { v = q.dequeue(); color[v.row][v.column] = black; for each (r,c) adjacent to (row,column) { if (maze[r][c]!='#' && color[r][c]==white) { q.enqueue(r,c); color[r][c] = gray; distance[r][c] = distance[row][column] + 1; pred[r][c] = vertex(row,column); } } } switch (color[exit_row][exit_column]) { case white: print("Exit is unreachable."); break; case black: print("Exit is reachable in "+distance[exit_row][exit_column]+" steps: "); print_path_to(exit_row,exit_column); break; }In the end, the array
pred
provides enough
information to reconstruct the path.
print_path_to (r,c) { if (pred[r][c]!=null) { print_path_to(pred[r][c].row,pred[r][c].column); } print("("+r+","+c+")"); }
for row from 0 to num_rows-1 { for column from 0 to num_columns-1 { color[row][column] = white; distance[row][column] = MAXINT; } } q = new PriorityQueue(); q.enqueue(start_row,start_column); color[start_row][start_column] = gray; distance[start_row][start_column] = 0; pred[start_row][start_column] = null; while (q.head != q.tail) { v = q.dequeue(); color[v.row][v.column] = black; for each (r,c) adjacent to (row,column) { if (maze[r][c]!='#' && color[r][c]!=black) { d = distance[row][column] + edge_length[row][column][r][c]; if (color[r][c]==white) { q.enqueue(r,c); color[r][c] = gray; distance[r][c] = d; pred[r][c] = vertex(row,column); } if (color[r][c]==gray && d < distance[r][c]) { distance[r][c] = d; push up vertex (r,c) in priority queue; pred[r][c] = vertex(row,column); } } } }
maze
, color
, distance
and pred
will all be 3-dimensional.
################### #.....############# #..##.############# #..##.############# #..##.############# #S.##............E# ###################
rows*cols
, how fast can a hopper get at most?
(x,y,vx,vy)
.(start_x, start_y, 0, 0)
.(exit_x, exit_y, ..., ...)
.u
and v
are connected, if the state v
can be reached from u
in one step.class vertex { int x; int y; int vx; int vy; } int color[num_rows][num_cols][num_speeds][num_speeds]; int distance[num_rows][num_cols][num_speeds][num_speeds]; vertex pred[num_rows][num_cols][num_speeds][num_speeds];
color
, distance
, or pred
. We have to use hashtables.Last modified 2001-02-12
mdettinger@arsdigita.com |