The mice that survived the harrowing hazards of island survival must be good at finding their way around so let’s stick one in the middle of a maze and let it find its way out.
Output is to be written to a text file named “Paths.txt”. First, you are to display the maze with an M at the initial location of the mouse. For each path out of a maze, display the maze showing the path from the initial location of the mouse to the exit. Display an M at the initial position of the mouse and in the remaining cells of the path, display the move number modulo 10. Following the output of all of the paths, write summary information including the number of paths, which path was the shortest (and its length), and which path was the longest (and its length). Here is an example of what the output should look like:
********** *** M** *** *** * *** **** * *** **** * *** **** * *** ** * *** ** *** *** *** *** ****** Solution #1 ********** *** M** *** ***12* *** ****3* *** ****4* *** ****5* *** **876* *** **9*** ***3210*** ***4****** Solution #2 ********** ***4321M** ***5*** * ***6**** * ***7**** * ***8**** * ***9** * ***0** *** ***1 *** ***2****** Summary Information ------------------- Number of paths: 2 Shortest path: #2 with 12 steps Longest path: #1 with 14 steps There may be additional paths with the fewest or most steps. This program records only the first such path.
An input file contains data for one maze. The first line records the number of rows (no more than 25) and columns (no more than 80) in the maze. The second line records the initial location of the mouse (row index followed by column index). The maze follows, one line per row. The impenetrable walls of the maze are represented by asterisks with the passageways represented by blanks. Here is the maze file that was used to generate the output given above:
10 10 1 7 ********** *** ** *** *** * *** **** * *** **** * *** **** * *** ** * *** ** *** *** *** *** ******
Your program should find all of the paths that lead from the initial location of the mouse to an exit. The mouse may move only horizontally and vertically; no diagonal movement is permitted. A path consists of a sequence of unique cells (no back-tracking and no looping) representing movements of the mouse and leading from the initial location to a location at the very edge of the maze. In the sample maze above, the mouse will have exited the maze when it reaches row index 9 and column index 3. You are also required to determine the length of each path (the number of movements required to get out of the maze), which path was the shortest (and its length), and which path was longest (and its length)
Using a recursive move function can facilitate the solution to the mouse in a maze problem. During a search for an exit, the mouse can attempt to move in one of three directions: to the left, straight ahead, or to the right. (Moving backwards is counterproductive because that would take the mouse back to its previous location.)
The move function would need to know the current location of the mouse and the direction (north, east, south, or west) that the mouse wants to move. Based on that information, the move function would calculate the new position of the mouse. There are three terminating conditions:
In each of these cases, the move function would terminate (which is why they are called terminating conditions) and return execution to the previous invocation (which represents the previous location of the mouse).
However, if none of these conditions is true, then the new location of the mouse is a non-exit location within the maze that the mouse has not yet encountered along its current path. That is, it has made some progress. From this new location, the mouse will attempt to move to the left, straight ahead, and to the right in its continuing quest to find an exit. Each of these moves is a recursive invocation of the move function.
In the main function, the mouse is just plopped down in the maze. In main, the mouse must try looking for exit paths in all four directions: north, east, south, and west. As noted earlier, once it begins moving, it only needs to try moving to the left, straight ahead, and to the right since going backwards is, in effect, a loop (the mouse returns to a spot it has already visited along its current path).
In the maze, a space character represents a location that the mouse can enter. In effect, then, any other character (such as an asterisk) represents a location the mouse cannot enter. I suggest that when the mouse moves to a blank space, you replace that blank with a single digit character (the number of moves modulo 10). If the mouse reaches that position again in its path (terminating condition 3) that location would be immediately recognized as a location the mouse can not enter since that location is not a space character. If you use this method to prevent going in circles, you must remember to change the current location back to a space before terminating the move function and returning to the previous location.
Name your program file "Hmwk02.cpp" and submit it to me as an email attachment.