Assignment #5: Maze Traversal
You are to solve the extended maze traversal problem discussed
in class.
Prompt the user for the name of the file that contains the maze.
The format of the maze file is given below.
For this assignment, assume that the starting point is
row 0, column 0, and the ending point is the last row, last column.
Then prompt for the wall-knocking penalty (see below).
Finally, print the cost of the shortest path, and its description.
Covers
Graph algorithms, binary heaps, two-dimensional arrays, advanced
Java programming.
Maze File
The first line contains the number of rows and columns.
Each subsequent line represents a square and possible walls:
N for northern wall, S for southern wall, E for eastern wall,
W for western wall. An eastern wall for square (i,j) implies
a western wall for square (i,j+1)
(if square (i,j+1) exists), whether or not square (i,j+1)
explicity says so, and so on for other directions.
Any square in row zero automatically has a northern wall;
similarly for other squares on the border, except for the
starting and ending points.
Each square may list several walls (or possibly no walls);
the directions can be in any order, and the squares can be in any order.
Example of an input file with a couple of redundant walls:
4 4
0 0 S
0 1 E
0 2 W
1 0 NS
1 2 ES
2 1 N
3 1 W
3 2 N
3 3 N
|
|
For this maze the shortest path is 13 squares,
and the path is given by the directions
ESENESSWWSEE.
(In other words, go east, then south, then east, etc.
Once you have numbered the maze squares by Dijkstra's
algorithm discussed in class, printing out the path is simple
if you use recursion.
Needless to say, you should catch any ill-formatted lines in the input file
and skip them after a printing a warning message.
Wall Knocking
In this assignment, you are allowed to knock down walls.
Knocking down a wall incurs a penalty P for each
wall knocked down.
You will need to prompt the user to enter the value of P.
Because walls may be knocked down, you are guaranteed that
a path exists.
Print the length of the shortest path
(the length includes penalties for knocking down walls) and
the sequence of steps taken to reach it. Also mention how many
walls are knocked down.
Observe that if the penalty is 0, then you may knock down walls
with impunity, and the shortest path is trivial.
If the penalty exceeds the number of squares in the maze,
then the shortest path is the path that knocks down the
fewest number of walls. For most of the mazes, that
you will be testing, this means
the shortest path with no walls knocked down.
For one of the mazes, this means knocking down one wall.
Most interesting is when the penalty is a small number, such as
15. In this case, for any interesting maze, you'll be hard
pressed to figure out the solution without the use of a computer.
Algorithm
The algorithm you will use is Dijkstra's algorithm (Chapter 14).
Because the Collections API includes a priority queue
starting in Java 1.5,
which is esssential for an efficient implementation,
you must use the Java 1.5
PriorityQueue class.
Submission Procedure
Submit all your source code, and the results of running the program
on ALL the test cases.