CS 211 - Fall 2012

Lab 9

Due: Monday, November 5, 2012

Maze Solver

For this lab, write a C program that will find its way through a maze using the depth-first search algoirthm and a linked list stack data structure.

The code to create the maze is already given to you at: maze.c

This program takes input from a file specified in the command line argument that contains two integer values per line of input:

  • The first line gives the size of the 2-D array
  • The second line gives the coordinates of the starting position in the maze
  • The third line gives the coordinates of the ending position in the maze
  • The remaining lines in the file gives the coordinates of blocked positions in the maze
The data file of data1 shows an example of such an input file. This input create the maze in this attached file: mazeout. The blocked positions and the edges of the maze are filled in with *'s. The start position is filled in with a 's'. The end position in filled in with a 'e'. The other positions are filled in with periods. The program can create a maze of any size up to 30x30. Also note that a maze of size NxN has valid coordinate values in the range from 1 to N.

The algorithm to find a path through the maze is as follows:

  • Mark all unblocked positions in the maze as "UNVISITED"
  • push the start position's coordinates on the stack
  • mark the start position as visited
  • While (stack is not empty and end has not been found)
    • if the coordinate at the Top of the Stack has an unvisited (and unblocked) neighbor
      • push the coordinates of the unvisited neighbor on the stack
      • mark the unvisited neighbor as visited
    • else
      • pop the coordinate at the Top of the Stack
  • If the stack is empty
    • The maze has no solution
  • else
    • The items on the stack contain the coordinates of the solution from the end of the maze to the start of the maze.
Once the algorithm is run, you must print out a message stating the maze has no solution or list the coordinates of the locations of the path in the maze from the start of the maze to the end of the maze that was found by the algorithm. Note this means printing out the contents of the stack in reverse order.

When refering to neighbors, those positions will be the ones abov, below, left or right of the current position (not diagonal). So for position x,y its neighbors are at:

  • x+1, y
  • x-1, y
  • x, y+1
  • x, y-1
The stack is to use a linked list structure of coordinates. The following code shows the skeleton of a listed list code with only a single integer as the value in each node: llist.c

Command Line Argument: Debug Mode

Your program is to be able to take one optional command line argument, the -d flag. When this flag is given, your program is to run in "debug" mode. When in this mode, your program is to display the values currently in the stack in proper order. Also, when the stack grows, you are to explicitly state the old and new size of the dynamic array as well as incidate the number of values copies from the current tot he new dynamic array.

When the flag is not given, this debugging information should not be displayed. One simple way to set up a "debugging" mode is to use a boolean variable which is set to true when debugging mode is turned on but false otherwise. Then usig a simple if statement controls whether information should be output.

if ( debugMode == TRUE )

printf (" Debugging Information \n");

Program Submission

Your are to submit the programs for this lab via the Assignments Page in Blackboard.

To help the TA, name your file with your net-id and the assignment name, like:

  • ptroy1LabX.c

Submit this file via the Assignment Link for the Lab in Blackboard.

  1. In the CS 211 Web Pages in Blackboard, go to the Assignments Page
  2. Click on the link for the correct lab. This will open a web page with the title: "Upload Assignment: Lab X", where X is the number of the lab
  3. Scroll down and click on the button "Browse for Local File"
  4. Select the file that you created that contains the program. Then click OK.
  5. Repeat steps 3 and 4 for your second program.
  6. Click the submit button on the "Upload Assignment: Lab X" page.
  7. You should see the Submission History page that shows what you submitted. Verify you actually submitted the correct information.

Check out the following code regarding simple creation of a dynamic array

Topic attachments
I Attachment Action Size Date Who Comment
Data1EXT data1 manage 0.1 K 2012-10-31 - 12:54 UnknownUser  
Cc llist.c manage 0.4 K 2012-10-31 - 14:01 UnknownUser  
Cc maze.c manage 1.8 K 2012-10-31 - 12:50 UnknownUser  
MazeoutEXT mazeout manage 0.5 K 2012-10-31 - 13:00 UnknownUser  
 
Copyright 2014 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
WISEST
Helping Women Faculty Advance
Funded by NSF