Description
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.
