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.
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.
You may and should use the BinaryHeap
class provided in the online code.
About Two-dimensional C++ Arrays
These are messy in the base-language C++.
It would be worthwhile to write a short template class to simulate
two-dimensional arrays.
Here is an acceptable matrix class.
Java programmers shouldn't have any problems with matrices.
Wall Knocking
In this assignment, you are now 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 9).
You will need to use a priority queue instead of a queue
to store potential squares to visit.
More details in class.
Make sure you are there...
Due Date
This assignment is due on Monday, July 26.
Submission Procedure
The mazes will be the same as before.
Sometime before the due date, I
will tell you which mazes to use, and what the
wall-knocking costs are.
Submit all your source code, and the results of running the program
on the test cases.