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:

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.