You are allowed to modify Maze.java and you must turn it in (along with VisitedState.java and EasyReader.java), whether you have modified it or not. If you want to modify VisitedState.java or EasyReader.java, talk to us (the staff) first.

You may not use/reference any existing (library etc.) data structure code/classes, except for built-in arrays. Exception: you may use your own code for any of the earlier homeworks.

Be sure to have your programs use the most efficient data structures and algorithms (from those covered in the class) that are appropriate for the tasks at hand. For example, you should use a priority queue when implementing Dijkstra's algorithm.

Here are examples of items #3 and #4 of the detailed results to be written to the output files. For #3, assume that the path goes through three rooms: the first with x=1,y=1 (the starting room), the second with x=1,y=2, and the last with x=2,y=2 (the exit room). The output then would look like so:

1 1
1 2
2 2

For #4, let's say your maze consists of two rows and three columns, and the weights that the algorithm computed are:

• First row: first room 11, second room 12, third room 13
• Second row: first room 21, second room 22, third room was not visited

 11 12 13
 21 22 -1