C++

Recursive Function to Solve a Maze

We describe a maze as having row X col cells. For example if row was 3, and col was 4, then we would have a grid of cells as follows. We describe a wall by the two cell numbers the wall separates (smaller number first). If every single wall existed, there would be (row-1)(col) + (col-1)(row) walls.

 0 | 1 | 2 | 3 ------------------- 4 | 5 | 6 | 7 -------------------- 8 | 9 | 10 | 11 

A Maze class (which you do not need to implement) describes a maze using the method described It has member functions that you can use to travel through the maze (ie figure out where you are, know what cells you can reach, etc.)

Write a recursive maze runner:

int runMaze(Maze& theMaze, int path[], int fromCell, int toCell);

The runMaze() function will find a path from cell number fromCell to cell number toCell. function will "markup" theMaze with the path and pass back an array containing the path (using the cell numbers) from the starting cell to ending cell. The function will return the number of cells along the pathway from the starting cell to the ending cell inclusive.

For example, suppose the fromCell was 0 and the toCell was 3 using the maze below:

 0 | 1 2 3 ---------- 4 5 | 6 7 ---- 8 9 10 | 11 

runMaze() function would put the following into path: {0,4,5,1,2,3} and return 6