Program: maze Solver

Description

This program will take in a maze input file with starting and ending locations marked on the maze. The program must recursively attempt to reach the end of the maze. A successful run through the maze should be highlighted and output to the screen.

SPECIFICATIONS

This program must use a struct to store the maze and a recursive algorithm to get full credit. Failure to use both will incur a 20% grade penalty. You may use a global variable to store the maze. You may use other algorithms to process the maze. However, the algorithms discussed in class are preferred.

INPUT

The maze matrix may be of any dimension less than 50 x 50. The starting location will be marked with an S and the ends with an F. There will always be at least one correct path through the maze. The name of the maze input file will be Maze.txt. The following is an example:

OUTPUT

There may be multiple correct paths through the maze. You will receive 5% extra credit for printing the length of the path you output. The length of the path is the number of characters BETWEEN the S and the E. You may also receive an additional 5% extra credit for developing and implementing an algorithm that always returns the shortest path possible (or one of the shortest paths if multiple paths are tied for the shortest path). You MUST mark the path through the maze with an X. You must name the file solvedMaze.txt, any other name will incur a massive penalty. In addition to writing a header containing your name and the solved maze to the output file, please output the solved maze to the screen along with a statement describing any extra credit you have earned.

The length of this path is 15 (5% EC).

This algorithm produces the shortest path (5% EC).

DELIVERABLES

Your program must process the inputs and produce a correct path to the end of the maze to receive credit. Name your program by last name, first initial, and mini-project-2. Thus, for Jonathan Leidig, the file name would be Leidig-J-Project-5.cpp. Make sure your code works with an input maze of any size and wall configuration. Hardcode the name of the input file into your program.

GETTING STARTED

//User-Defined Structure

struct Maze{

//Define Maze

};

//Global Variable

Maze myMaze;

int main()

{

//Open input file maze.txt, output file

//Read in the maze.

//Write the file header

return 0;

}

//Recursive method that attempts to move in different directions and returns if the end of the maze was found.

//Return 0 for path not successful, 1 for F was reached.

int maze_Solver (char previousDirection, int X, int Y)

{

//End conditions - F reached

//return 1

//Check if North, South, East, West (not including the previousDirection) can be traversed

//Recurse maze_Solver calls in valid directions

//When true is returned by a recursive call

//Mark the current X,Y index with an X

//return 1

return 0;

}