Due at the start of class on Monday October 7
In lab 4, you'll be
The prelab questions are related to linked queues and solving a
maze. Please write or type up your solutions, and hand in
a paper copy by 10 am on Monday. Sign the Honor Pledge
somewhere on your paper. Late prelabs are not accepted.
In lab 4, you'll be writing your own Queue class, implemented
as a linked list of nodes, as shown below:
Make a copy of the above sketch of q1. List the steps
that would be required to enqueue the value E onto q1, and
show the changes in your sketch.
Draw a sketch of a second linked queue q2, this one containing the values X, Y, and Z. Then show the changes that you would need to make to append q2 to q1. You should do this just by altering some of the object references in the diagram, not by creating any new nodes.
How many changes were needed? List them.
In this lab you will also be writing a program that will read in a maze and then find a path from the start to the exit.
First let's talk about a typical maze. It has walls and pathways, and it has one (or more) starting point(s) and one (or more) exit point(s). (To keep things simple, let's just assume it has no more than one of each.) Furthermore, one wall is just like another, and any open space (not including start and finish) is also identical. So, we can think of a maze as being made up of individual squares, each square either empty, a wall, the start, or the exit.
Below is a graphical representation of a maze. The green box represents the start, the red box the exit, and the black squares the walls.
The rest of the file will be R rows of C integers. The value of the integers will be as follows:
0 - an empty space 1 - a wall 2 - the start 3 - the exit
In terms of coordinates, consider the upper left corner to be position [0,0] and the lower right to be [R-1,C-1].
For example, this is the text version of the maze above (start is at [6,4] and exit at [6,11]).
7 13 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 1 0 1 0 0 0 0 0 2 0 0 1 0 0 1 3 0
Write a Java program which reads a maze description like the
one above and stores it in a two-dimensional array of
integers. When if finishes reading, it should print the
contents of the array in the same format.
The input should be read from System.in (use a Scanner) and
the output should be written to System.out.
The application portion of this lab will be to write a MazeSolver class, which will try to solve a given maze; that is, to find a path from the start square to the finish square (without jumping over any walls). The algorithm one usually follows goes something like this: start at the start location and trace along all possible paths to (eventually) all reachable open squares. If at some point you run across the finish, it was reachable. If not, it wasn't.
In pseudocode, we have the following:
At the start
Each step thereafter
This pseudocode will work correctly, no matter what kind of
worklist you use (i.e., a stack or a queue).
|at the start||after step 1||after step 2||after step 3||after step 4||after step 5||after step 6||after step 7||after step 8|
|worklist as a stack||
|newly visited square||N/A||(6,4)||(6,3)||
If you adhered to the honor code in this assignment, add the following statement at the top of your prelab.
I have adhered to the Honor Code in this assignment.
Write or type your solutions and hand in a paper copy
by the deadline listed at the top of this prelab. Late
prelabs will not be accepted.