CPSC 170 Spring 2003
Program 3: Traversing a Maze
Due Friday, April 4

Overview

Imagine a maze represented by a two dimensional array as follows:

A 1 in the array represents an open route.
A 0 in the array represents a closed route.
The person traversing the maze ("the rat") starts at the upper lefthand corner (0,0). The goal is to reach the lower righthand corner. The array need not be square.
From each cell, the rat can move up, down, left, or right. Of course, it can only move to another open cell, and cannot move off the board. No diagonal movement is allowed.

For example, consider the maze below:

   1 1 1 1 1 0
   0 1 0 0 1 1
   1 1 0 0 0 0
   0 1 1 1 1 1

In this maze, there is only one route to the end, marked by stars below:

   * * 1 1 1 0
   0 * 0 0 1 1
   1 * 0 0 0 0
   0 * * * * *

In general, there might be more than one route to the end, and of course there could be an arbitrary number of dead ends.

Your assignment is to write a program to traverse such a maze.

Program Structure

Most of the work will be in a Maze class, which should contain the following public methods:

void readMaze(String filename) throws IOException -- reads the maze from the given file.
String toString() -- returns the maze in a format like that shown above.
void traverse() -- traverses the maze, modifying it so that cells that are visited are marked with a *. Note that not only the final route will be marked with *; all dead ends that were attempted will be marked as well.

You will also need a TestMaze class that will do the following:

Create a new Maze object
Prompt the user for a filename
Read the maze from that file
Print the initial maze
Traverse the maze
Print the traversed maze

Approach

One way to traverse a maze is using a stack. We will discuss this in more detail in class, but the strategy is simple. The program keeps a stack of cells to try next. It processes these with a loop that basically does two things:

Pops the top cell from the stack and marks it visited.
Checks to see if the popped cell is the end of the maze. If not, pushes all adjacent cells that are open and have not yet been visited.

You must write your own stack class that implements the Stack interface using a linked representation. Do this first, and test it thoroughly before you try to use it in the Maze program.

Input and Output

The first line of the input file will contain the number of rows in the maze; the second line will contain the number of columns in the maze. Subsequent lines will store the maze itself, one row per line, with no spaces between elements. You will need to set up a FileReader to read from the file, and you will probably want to create a BufferedReader from the FileReader so that you can use its readLine() method. Since readLine() returns a string, you will then need to transfer the characters in the string to the array representing the maze. Remember that both the readMaze method and the main method in the TestMaze class will need to include throws IOException in their headers. You will also need to import java.io.* in both files.

For the maze given above (which would be preceded by the values 4 and 6 on separate lines in the input file), your program might produce the following output:

Original maze
-------------
1 1 1 1 1 0 
0 1 0 0 1 1 
1 1 0 0 0 0 
0 1 1 1 1 1 

Traversed maze
-------------
* * * * * 0 
0 * 0 0 * * 
1 * 0 0 0 0 
0 * * * * *

Note that in this case only one dead end -- the one still marked with a 1 -- was not tried before the solution was found. The actual routes that your program tries will depend on the order in which you push the options onto the stack, so your output may look different.

What to Turn In