Warning: This assignment is much harder than IPA 1-1. You must start as soon as possible. Expect to spend at least twenty hours for this assignment. You should develop an algorithm before writing code.
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 tests cases here does not guarantee a full score. You are responsible for creating test cases that meet the specification but are not included here.
If you need more mazes, please 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 file here. You must use the skeleton file to develop your code. You are allowed to do the following
You can add functions in all files.
You can edit (add input parameters, delete input parametes, change parameter types, change return values) for all functions in all files.
You can add new files.
You need to modify Makefile if you add new files.
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 IPA1-2, your program needs to read the maze file and then traverse the maze from start to finish. The program needs to print the route you took.
Strategy
As you are thinking about how to find the exit, you are thinking about the courses that have taught you problem-solving skills. You need to remember where you have been and to avoid visiting the same place twice. Every time you encounter an intersection, you have to remember the decision made at this intersection. You do not know the size of the maze so you have to store data of an unknown size. Fortunately, you have developed a survival strategy:
Go as far as possible until reaching the exit or a dead end.
Whenever you encounter an intersection, you rely on your compass (GPS doesn't work underground but fortunately your compass still does). You try different routes at an intersection in the following order:
East -> South -> West -> North
You should not take a direction that would lead you back to where you have been, unless you encounter a dead end.
After reaching a dead end, go back to the last intersection and take a different route, following the direction order listed above. For example, if you comes from the West and encounter an intersection. You have the choices of going East or South (not North). You should try to go East first. If this choice reaches a dead end, come back to this intersection and go South.
If all routes at an intersection reach to dead ends, go back to the previous intersection.
This strategy is called depth-first-search with backtracking because you go as far as possible and backtrack when a route turns out to be a dead end. If you follow this strategy, it is possible to show that you will eventually always find the exit (if there exists a path from the starting point to the exit in the first place, that is).
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_2' (case-sensitive, no extension, not ipa1_2.exe).
Your code needs to follow the coding standards specified here. We will manually check this and you can lose points if standards are not followed. You can find examples of how to follow the coding standards here.
Your program will read the maze file and keep track of all necessary information in memory.
Your algorithm must meet the strategy requirements in the [Strategy] section. It is very important that your solution follows the order: East -> South -> West -> North. If your program takes a different order, the output will be different and you will receive zero points on the assignment.
For each step, print out a string "Move to (row,col)\n" where (row,col) is the coordinate of the new location. The player can move only one step each time, i.e., from (row,col) you can only reach (row+/-1,col) or (row,col+/-1) as your next step. Here, row corresponds to the vertical coordinate and col corresponds to the horizontal coordinate.
The first step must be "Move to (row0,col0)\n" where (row0,col0) is the coordinate of the starting location 's', and the last step must be "Move to (row1,col1)\n" where (row1,col1) is the coordinate of the exit 'E'.
Assumptions
The top-left block of the maze has coordinate (0,0). This is the convention in computers.
The maximum width (number of columns) of a maze does not exceed 80. For IPA1-2, there is no predefined limit for the height (number of rows). Your program has to decide the height of a maze.
The maze is always fully enclosed by bricks, i.e., it is impossible to escape from the maze other than through the exit. A valid maze is always rectangular.
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.
Hints
You are encouraged to use structures for this assignment. A structure about the maze should include the relevant information such as the location of the exit, the current location, the cells, etc.
We will check whether your program initializes all pointers to NULL. This can be accomlished in the following ways
int * ptr = NULL; /* initialized to NULL, required */
int * ptr;
ptr = NULL; /* immediately after declaring ptr */
int * ptr = malloc(numberElement * sizeof(int));
If you write the following code without initialization, you will lose 0.2 point.
int * ptr; /* uninitialized pointer. NOT ALLOWED */
Why do we check this? Uninitializing pointers make a program's behavior unpredictable.
(You are also allowed to declare and allocate memory for a pointer immediately using malloc() or calloc().)
You should consider to create a new data type (using typedef struct) to put related data together. For example, instead of using four unrelated integers for exitRow, exitColumn, startRow, startColumn, you can create a structure for them. This is specially helpful when you need to pass the information to functions.
Sample Output
Here is one of the possible mazes.
*****
* s*
* ***
* *
*E***
For the example maze shown above, the program should produce the following outputs.
Move to (1,3)
Move to (1,2)
Move to (1,1)
Move to (2,1)
Move to (3,1)
Move to (3,2)
Move to (3,3)
Move to (3,2)
Move to (3,1)
Move to (4,1)
What to submit?
Your submission should be created by typing "zip ipa1_2.zip ipa1_2.c ipa1_2print.c utility.h utility.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_2" 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 (other than .) 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. Click here for more debugger information.
