CS 127, Assignment #3

This assignment is due by 11:10 AM, Wednesday, January 31. Submit it using HSP.

The Assignment

Your main goal for this assignment is to write a function that will take a maze as input, and print the solved maze. So, for example, your function will take some representation of this maze as input:

 ___ ___ ___ ___ ___
|               |   |
|               |   |
|    ___     ___|   |
|   |   |   |   |   |
|   |   |   |   |   |
|   |   |___|   |   |
|       |           |
|       |           |
|    ___|    ___    |
|           |       |
|           |       |
|___ ___ ___|___ ___|

and print this maze as output.

 ___ ___ ___ ___ ___
|               |   |
| S             |   |
|    ___     ___|   |
|   |   |   |   |   |
| * |   |   |   |   |
|   |   |___|   |   |
|       |           |
| *     | *   *   * |
|    ___|    ___    |
|           |       |
| *   *   * |     F |
|___ ___ ___|___ ___|

More precisely, I want you to use the following as the core of a header file "maze.h", and write code for the functions GetMaze(), PrintMaze(), and PrintSolvedMaze().

#define		MAZE_MAX	50

typedef struct
{
	int		squaresAcross;
	int		squaresDown;
	int		horizontalWall[MAZE_MAX][MAZE_MAX];
	int		verticalWall[MAZE_MAX][MAZE_MAX];
} maze;

void GetMaze( FILE *, maze * );
void PrintMaze( maze * );
void PrintSolvedMaze( maze * );

GetMaze() should take a file pointer as input, and return a maze via its second parameter. It is the responsibility of the calling routine to open the appropriate text file. That responsibility might be carried out like this:


     FILE       *theMazeFile;
     maze       myMaze;
     char       fileName[20] = "mazefile.txt";

     theMazeFile = fopen( fileName, "r" );  /* open for reading */
     if( theMazeFile == NULL )
     {
        printf( "Can't open %s.\n", fileName );
        exit( 1 );
     }
	 
     GetMaze( theMazeFile, &myMaze );

PrintMaze() should print the given maze without the *'s.

PrintSolvedMaze() should print the given maze with an S (Start) at the upper left (position (1,1)), an F at the bottom right (position (width,height)), and *'s along the solution path your program computes.

Maze file format

Assume the maze file is organized like this: first a line with the number of rows and the number of columns, then a line to be ignored, then a bunch of lines of 0's and 1's indicating where the horizontal walls are, then another line to be ignored, and finally a bunch of lines indicating where the vertical walls are. The maze above, for example, would be represented like this:

4 5
The horizontal walls:
1 1 1 1 1
0 1 0 1 0
0 0 1 0 0
0 1 0 1 0
1 1 1 1 1
The vertical walls:
1 0 0 0 1 1
1 1 1 1 1 1
1 0 1 0 0 1
1 0 0 1 0 1

Note that walls are indicated by 1's. Your GetMaze() function should index the horizontalWall[][] and verticalWall[][] fields so that the first index represents the row, and the second represents the column.

Algorithmic advice

That's it for the assignment. But now, how are you going to go about computing a solution? Try something like this:

Push the square (1,1) on an empty stack, and mark (1,1) as having tried WEST and NORTH.
While the stack is not empty and the square on top of the stack is not (width,height), do the following:
- If the square on top of the stack is marked as having tried all four compass points (NORTH, EAST, SOUTH, WEST), then pop it.
- Otherwise, find a direction the top square has not tried. Let's pretend, for example, that the top square is called S, and it has not tried EAST. If there is a wall to the east of S, mark S as having tried EAST. If there is not a wall to the east of S, mark S as having tried EAST, push the square to the east of S onto the stack, and mark that new square on top of the square as having tried WEST (the new square should not, after all, try heading back to S--that could start an infinite loop of walking east, then west, then east, then west,...).
  Act similarly for the other compass directions.

Start early, keep in touch, and have fun.

Jeff Ondich, Department of Mathematics and Computer Science, Carleton College, Northfield, MN 55057
(507) 663-4364, jondich@carleton.edu