Description
For this project, write a C program that will find its way through a maze using the depth-first
search algorithm. This program takes input from a file where the filename is specified in the
command line arguments. The input file will only contain two integer values per line of input:
• The first valid line gives the size of the 2-D maze (the number of rows given by the first
number, then the number of columns given by the second number), valid values are >= 1
• The second valid line gives the coordinates of the starting position in the maze
• The third valid line gives the coordinates of the ending position in the maze
• The remaining valid lines in the file give the coordinates of blocked positions in the maze
If the command line arguments do not contain a valid filename, you should print an error message
to STANDARD ERROR and quit the program. This could be because there was not a name given
or the name given did not match that of a valid file. If the command line arguments contains
multiple names, we leave it up to you to come up with a “good solution”. Ideas on such a “good
solution” could be:
• Use one of the names as the input file and proceed (pick which name makes most sense to
use – i.e. use the first filename given or use the last filename given).
• Give an error message stating that too many names were given and quit.
• Run the program to solve the maze given with each filename.
The following shows an example of such an input file. The coordinates are given with the row
listed first and the column listed second. A maze of NxM has rows numbered from 1 to N and
columns number from 1 to M.
10 20
1 1
10 20
5 1
4 2
3 3
1 10
2 9
3 8
4 7
5 6
6 5
7 4
8 3
CS211 – Programming Practicum Spring 2019
The above input creates the following maze will 11 blocked positions:
size: 10, 20
start: 1, 1
end: 10, 20
**********************
*s……..*……….*
*……..*………..*
*..*….*…………*
*.*….*………….*
**….*…………..*
*….*……………*
*…*…………….*
*..*……………..*
*………………..*
*……………….e*
**********************
The blocked positions and the edges of the above maze are filled in with *’s. The start position is
filled in with an ‘s’. The end position in filled in with an ‘e’. The other positions are filled in with
periods.
You may assume that the input will always have two integer values per line; however, the values
may be out of range. If an invalid value is given on an input line, print a descriptive error message
to STANDARD ERROR, ignore those two input values and continue processing input using the
next line of input. Any value of zero or less is invalid in this program. For a coordinate value in
the maze, valid value range from 1 to the maximum row size or column size. Also, the starting
and ending positions of the maze must never be blocked. Since errors may exist:
• The size of the maze is on the first valid line of input.
• The starting position of the maze is the second valid line of input.
• The ending position of the maze is the third valid line of input.
If the file ends before getting 3 valid lines of input, print out an error message to STANDARD
ERROR and quit the program.
Input with invalid values is shown below. The comments on each line are not part of the input, but
there to help explain the error.
10 0 => Invalid: Maze sizes must be greater than 0
15 7 => Maze becomes size 15 x 7
10 20 => Invalid: column 20 is outside range from 1 to 7
5 1 => Starting position is at position 5, 1
24 2 => Invalid: row 24 is outside of range from 1 to 15
3 3 => Ending position is at position 3, 3
1 10 => Invalid: column 10 is outside range from 1 to 7
2 9 => Invalid: column 9 is outside range from 1 to 7
3 8 => Invalid: column 8 is outside range from 1 to 7
4 7
5 6
5 1 => Invalid: attempting to block starting position
6 5
7 4
CS211 – Programming Practicum Spring 2019
The algorithm you are to use to find a path through the maze is a Depth First Search. You MUST
use the following form Depth First Search. You are NOT allowed to use a recursive version of the
depth first search (since you are required to use your own linked list stack to solve this).
• 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)
o if the coordinate at the Top of the Stack is the end position
§ then end has been found (break out of loop)
o if the coordinate at the Top of the Stack has an unvisited (and unblocked) neighbor
§ push the coordinates of one unvisited neighbor on the stack
§ mark that one unvisited neighbor as visited
o else
§ pop the coordinate at the Top of the Stack
• If the stack is empty
o The maze has no solution
• else
o The items on the stack contain the coordinates of the solution from the end of the
maze to the start of the maze.
When referring to neighbors, those positions will be the ones above, 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
Your program is to first output the size of the maze, the start and ending coordinates and an ASCII
drawing of the maze. The code maze.c does this for any maze of size 30X30 or less. The maze.c
program uses a static sized 2-D array; however, your program MUST use a dynamic 2-D array
sized to reflect the maze size given in the input file. You must also dynamically deallocate this
array at the end of your program. The maze.c program also does not do any error checking for
invalid input, your program MUST check for invalid input.
Once the maze solving algorithm is run, you must then print out a message stating either:
§ the maze has no solution
or
§ listing 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.
The stack MUST use a linked list of coordinate values. The head of the linked list MUST NOT
be global. It must be declared as a local variable in main( ) or some other function. You may
create a structure to contain the head of the stack if you desire but again the initial instance of the
structure must be a local variable. The code for each stack operation MUST be done in its own
function where the head is passed in as a parameter. The only exception to this is that the initializing
function may return a newly created instance.
CS211 – Programming Practicum Spring 2019
You MUST write functions for the following operations (these are the “same” functions as Project 2):
• initializing the stack,
• checking if the stack is empty,
• pushing an element onto the stack,
• popping an element off of the stack,
• accessing the top element on the stack, and
• resetting the stack so that it is empty and ready to be used again.
These functions must NOT contain memory leaks! Expect points deducted if your code fails in this
regard. (Valgrind will be used when grading.)
Command Line Argument: Debug Mode
Your program must 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 coordinates of the maze positions as they are pushed onto the stack and popped off the
stack if the Top of Stack coordinate does not have an unvisited (and unblocked) neighbor. When
the flag is not given, this debugging information should not be displayed.
Since the input file for the maze also comes from the command line arguments, you may not
assume which order in which the command line arguments are given. Thus the command line
arguments may be given as:
• ./a.out mazeInput.txt
• ./a.out mazeInput.txt -d
• ./a.out -d mazeInput.txt
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 using a simple if statement controls
whether information should be output or not.
if ( debugMode == TRUE )
printf (” Debugging Information \n”);
Optional ways for writing this code can be seen on the course website.
CS211 – Programming Practicum Spring 2019
Coding Style
Don’t forget to use good coding style when writing your program. Good coding style makes your
program easier to be read by other people as the compiler ignores these parts/differences in your
code. Elements of good code style include (but may not be limited to):
• Meaningful variable names
• Use of functions/methods
• Proper indentation
• Use of blank lines between code sections
• In-line comments
• Function/method header comments
• File header comments
The Code Review Checklist also hints at other elements of good coding style.
Program Submission
You are to submit the programs for this project via the Assignments Page in Blackboard.
To help the TA, name your file with your own net-id and the assignment name, like:
• netidProjX.c