Imagine that you are an intrepid adventurer that goes looking for hidden treasure in the far-off caves of lost civilization. As part of this quest, you become trapped in an underground maze. You are convinced that the treasure is somewhere in the maze, but you can see nothing but walls. You realize that you must have a strategy and a computer program to find the treasure. Unfortunately, no built-in Unix command would help you traverse a maze, so you must write a C program to do this.
In the example maze in the figure above, the red square is the exit of the maze (leading to the hidden treasure). The blue circle is the current location. The green circles mark the visited intersections. The yellow circles mark the visited locations.
Purpose
To traverse a maze to find the exit and back tracking (algorithm) whenever reaching a dead end.
Maze Structure
Here are some maze examples. The characters represent
'*': brick
' ': (space) corridor
'E': exit, i.e. the destination
's': your starting location (notice: lower case 's', not upper case)
Please be aware that these examples are not the cases to be used in grading. Passing all test cases in the skeleton files does not guarantee a full score.
If you need more mazes, please use some tools to generate one, like this Online Maze Generator. You may need to change the output a little to satisfy the assumptions.
Demonstration
Download the skeleton files here. You must use the skeleton files to develop your code.
This may be the most complex program you have ever written. To help you manage the assignment, this assignment is divided into two parts. In this IPA1-1, your program needs to read the maze file and print the following information:
The size of the maze: the height (number of rows) and the width (number of columns).
The location of the exit.
The location of the starting point.
Check whether a certain location is a brick.
Check whether a certain location is inside the maze.
Requirements
The program takes one input argument as the maze file. If this input file name is not provided, the program prints an error message and terminates with return value EXIT_FAILURE. If the file cannot be opened, it also prints an error message and returns EXIT_FAILURE. This constant is defined in stdlib.h and your program needs to include that header file.
You must include a Makefile in your submission. Your program will be compiled and built using your Makefile. The name of the executable file must be 'ipa1_1' (case-sensitive, no extension, not ipa1_1.exe).
Your code should follow the C coding standards expressed here. Faillure to abide these standard will result in loss of points. We will manually check whehter you follow the rules. You can find a guide with good programming practices here.
Your program cannot contain any global or static variable.
Assumptions
The top-left block of the maze has coordinate (row, column) = (0,0). This is the convention in computers.
Moving right increases the column by one. Moving down increases the row by one.
The maximum width (number of columns) of a maze does not exceed 80. For IPA1-1, you can assume the maximum height (number of rows) also does not exceed 80.
The maze is always fully enclosed by bricks, i.e., it is impossible to escape from the maze other than through the exit.
The starting location may appear anywhere in the maze, even at an intersection.
Each maze has at most one starting location and one exit. It is possible for a file to contain an invalid maze that has no starting location, no exit, or neither.
All passages (corridors) in mazes are 1-character wide.
There is one and only one path between two points in the maze.
All mazes are rectangular.
Hint
If you reach the end of a file, you can use fseek function to set the file pointer to the beginning of the file.
You should use the PritntResult Function in the skeleton code to pritnt all the resutls. The output has the following formats:
printf ("Start at (%3d,%3d)\n", row, col);
printf ("Exit at (%3d,%3d)\n", row, col);
printf ("(%3d,%3d) is a brick\n", row, col);
printf ("(%3d,%3d) is bounded\n", row, col);
printf ("Maximum row is %3d, Maximum column is %3d\n", row, col);
Remember to close the file before the program terminates. Otherwise, you will get an error called "memory leak."
You can add additional functions inside mazefunction.c (not in ipa1_1.c).
Sample Output
Here is one of the possible mazes.
*****
* *
* ***
* *
*E***
For the example maze shown above, the program should produce the following outputs.
Maze is invalid due to a missing starting/exit point
Exit at ( 4, 1)
Maximum row is 5, Maximum column is 5
( 0, 0) is a brick
( 0, 0) is bounded
( 0, 1) is a brick
( 0, 1) is bounded
( 0, 2) is a brick
( 0, 2) is bounded
( 0, 3) is a brick
( 0, 3) is bounded
( 0, 4) is a brick
( 0, 4) is bounded
( 1, 0) is a brick
( 1, 0) is bounded
( 1, 1) is bounded
( 1, 2) is bounded
( 1, 3) is bounded
( 1, 4) is a brick
( 1, 4) is bounded
( 2, 0) is a brick
( 2, 0) is bounded
( 2, 1) is bounded
( 2, 2) is a brick
( 2, 2) is bounded
( 2, 3) is a brick
( 2, 3) is bounded
( 2, 4) is a brick
( 2, 4) is bounded
( 3, 0) is a brick
( 3, 0) is bounded
( 3, 1) is bounded
( 3, 2) is bounded
( 3, 3) is bounded
( 3, 4) is a brick
( 3, 4) is bounded
( 4, 0) is a brick
( 4, 0) is bounded
( 4, 1) is bounded
( 4, 2) is a brick
( 4, 2) is bounded
( 4, 3) is a brick
( 4, 3) is bounded
( 4, 4) is a brick
( 4, 4) is bounded
What to submit?
Your submission should be created by typing "zip ipa1_1.zip ipa1_1.c mazefunction.h mazefunction.c Makefile README".
You will receive zero if everything is in a single file. Of course, you cannot submit three files and two of them are empty.
You will receive zero if there is no executable named "ipa1_1" after running "make".
README to explain what you have done and how you do it. It is a text file readable You need to explain how you store the locations. The file name must be README, not readme, not Readme, not README.txt, not README.pdf, nor README.doc.
Do not include object files, executable files, sample inputs, or outputs.
You should never have a space or symbol (underscore is acceptable) in a file name. Some operating systems can accept file names with spaces or symbols but some operating systems cannot. To make sure your programs work, do not take a chance.
Debugger
Debugger is a very useful tool to find errors in your code. This is a video showing how to use gdb. Click here for more debugger information.
