# CSCI 151 - Prelab 4

Due at the start of class on Monday October 7

In lab 4, you'll be

• implementing a queue with a linked list, and
• using a stack and queue to solve a maze

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:

Question 1:

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.

Question 2:

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.

## Representing a Maze

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.

We can represent such a maze with a text file of the following format. The first line of the file contains two integers. The first indicates the number of rows (R), the second, the number of columns (C).

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
```

Question 3:

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.

## Solving a Maze

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

• Create an (empty) worklist (stack or queue) of locations.
• Add the start location to it.

Each step thereafter

• Is the worklist empty? If so, the finish is unreachable; terminate the algorithm.
• Otherwise, grab the "next" location to explore from the worklist.
• Does the location correspond to the finish square? If so, the finish was reachable; terminate the algorithm and output the path you found.
• Otherwise, it is a reachable non-finish location that we haven't visited yet.  Then,
• mark the location as "visited",
• make a list of this location's neighbors; that is, all the adjacent locations (up, right, down, left) that are inside the maze and aren't walls, and
• add them to the worklist for future reference provided they have not previously been added to the worklist

This pseudocode will work correctly, no matter what kind of worklist you use (i.e., a stack or a queue).

Question 4:
Run this algorithm on the example maze shown above, using a stack as your worklist.  Run it for the first 8 steps; show your worklist after each step, as well as list (at each step) which squares have been visited.  To make grading life easier, please push adjacent squares onto the stack in the clockwise order given, namely, up, right, down, then left. Some of the entries are already filled in, so that you can tell if you are on the right track.

Coordinates are in (row, col) order. Be careful to stick to that order

 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 (6,4) (6,3) (6,5) (6,2) (6,5) (4,2) (3,0) (6,5) newly visited square N/A (6,4) (6,3)

We don't ask you to hand it in, but you should think about what these steps would be like for a queue rather than a stack.

## handing in your prelab

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.