Description
Programming Language : C
AIM
In this experiment you will have a chance to learn some data structures. You’re expected to implement
a program that finds a solution path of the given maze.
PROBLEM
Mazes have been an intriguing subject for many years. Experimental psychologists train rats to search
mazes for food, and many a mystery novelist has used an English country garden maze as setting for a
murder. We also interested in mazes since they present a nice application of matrices and stacks. You
are going to develop a program that runs a maze. Although this program takes many false paths before
it finds a correct one, once found it can correctly rerun the maze without taking any false paths.
In your program, the first issue that confronts us is the representation of the maze. The obvious choice
is a two dimensional array in which zeros represents the open paths and ones the barriers. On the
maze the capital letters denote doors and the small letters denote keys used for unlocking the doors.
Same letters represent key-door pairs (a > A, b > B, etc). Your program needs to find a key to open the
corresponding door. You should specify in the path.txt file which key is found. Figure-2 shows a simple
maze. You are expected to implement a program that finds a solution among the possible paths. You
should use these letters for moves in the path.txt file: E for East, W for West, N for North and S for
South. The Start and Exit points should be on the first and last row on the maze, respectively. The
letters S is used for Start and E for Exit (Our example shows that Start point is at top left, Exit is at
bottom right). Let X marks the spot of our current location and then Figure-1 shows the possible moves
from this position. So you have four directions of movements (except borders).
Figure-1. Allowable moves.
Some important issues:
Your program must find a possible solution path.
Maze size is not constant (but maximum 30 by 30).
Input Command: ./ maze.txt
INPUT
Your program takes one input file. Example maze.txt file is below. Several input files will be used to
explore your application’s robustness level;
Figure-2. Example maze.txt
OUTPUT
After execution, output of the program is written to a file named path.txt. It contains ONE possible
solution path of the maze (If there is no solution, it must be stated);
Figure-3. path.txt
Path looks like this (just example to clarify how to move):
Figure-4. Visualizing path to clarify
REPORTS
Your reports must be PDF documents and adhere to the Hacettepe University Computer Science
Department Report Writing Guidelines. Submissions with poorly written code can’t be expected to
receive a high score for the report. Here are some additional guidelines that will help you write your
report for this experiment:
Maximum number of report pages should be 4.
Briefly explain what you understand from the problem.
Provide a detailed description of your solution.
Do not copy-paste from the experiment sheet.
NOTES
Regardless of the length, use understandable names to your variables, functions, etc.
Write readable source code block.
Write comment lines when necessary.
Save all your work until the experiment is graded.
The assignment must be original, INDIVIDUAL work. Duplicate or very similar assignments are
both going to be punished. General discussion of the problem is allowed, but DO NOT SHARE
answers, algorithms or source codes.
The experiment code will be tested on the dev machine. Your source code should be compiled
with GCC. Otherwise your experiment will not be evaluated.
You can ask your questions through class’ piazza page.
SUBMISSIONS
Your submission will be in the format below:
o report
report.pdf
o source
maze.c
You will use online submission system to submit your experiments.
https://submit.cs.hacettepe.edu.tr Other submission methods (such as e-mail) will not be
accepted.
