Program #2 - Maze Traversal
Maze Traversal:
You will be given two files that contain ASCII mazes, and your program should first read in the maze into arrays (or vectors) and then recursively find a path through the maze. When the program has found a path through the maze it should print to the screen the path that it found. Your path can only be up, down, left or right (sorry no diagonal moves). For your final path you are not allowed to step on a square more than once (so treat previously marked squares as impassable).
Your program should prompt the user for the file name that contains the maze, and then proceed to read in the file. The format of the file is that the first line will contain information about the numbers of rows and the number of columns for the maze.
Key to the maze characters:%wall
.empty floor
eentrance (starting position)
xexit (ending position)
+step that your program takes....mark your trail as you go....and don't forget to erase
your marks if you need to go back
Here is what maze2.txt looks like:
15 x 28
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%...%.....%.......%........%
%......%....%.......%%%....%
%..%%..%%......%......%....e
%%%%%.%%%.%%%.....%...%%...%
%......%%....%...%.......%.%
%..%%%%.....%....%....%%%..%
%.....%%....%%...%%%%....%%%
%..%%%%%%%....%.%.%........%
%...............%..........%
%%%%%.......%...%..%..%%%%%%
%.....%.%...%%%....%.......%
%%%....%....%....%%%....%%.%
%%....%.%.%...%.....%%%....%
%%%%x%%%%%%%%%%%%%%%%%%%%%%%
Hints:
As you read in the maze you may want to save the location of the starting position.
Think about the solution first and write some pseudo-code before trying to write the recursive part of the solution.
what is your ending condition
what do you want to try each time you call the function
what happens in your function each time it is successful, or each time it is unsuccessful?
One way to solve it is to have your function declaration something like this: bool takeStep( int row, int col); where the function returns true if it finds the end (through a chain of calls) or false if this path is a dead-end.
Remember where a function call will return when it is done (successfull or not).....back to it's calling point.
Debugging Suggestions: For debugging feel free to make a smaller maze (5x5) to see if your algorithm works, or even a maze with no internal walls. Also it is always a good idea to print out the maze after every step or two so you can see the progress of you program (you can read a char into a junk variable to cause a pause in your program).
Turn in: A print out of your code, and the two mazes with your path. The two mazes you can capture from the command window (black screen) by using Select All and then Copy from the command windows menus, then you can paste your output below your programs code as a comment.
