Need a little help
 

We got this problem yesterday. Our teacher said if we get it done before October he'll give us extra credit, but I don't really even know where to start. Just point me in the right direction por favor. Here's the problem:

Maze Surfing

You dirty rat. You're caught in a malicious lab experiment, and dropped into a maze. Your job is to find the cheese and thereby to prove your superior intelligence of the various rodent sopecies.

Program Input

The input file PROG13.IN describes a single maze. The first line of the file is an integer, N, indicating the number of rows and columns in the maze, constrained by: 8 < N < 19. The next N lines each contain N characters seperated by spaces. Walls are represented by '#', hallways by '.', the start position by 'M' and the cheese by 'C'.

Program Output
The program should write the maze to PROG13.OUT, drawing the shortest path from M to C with a series of '+' characters. You may assume that (1) there will be a valid path from M to C, and (2) there will only be one path from M to C (i.e., no loops). The path is not permitted to contain any diagnol movements.

Sample Input:

Sample Output:

If you give the mouse a "facing" direction (say, north = 0, west = 1, etc) then you can do something like the following:

Anytime you call the "Move Forward" function, you toggle the current floor marker (. or +), then move your ghosted mouse to the next tile. This will "clear" the marker if you hit a dead end. The mouse will try all possible places (luckily there are no loops..).

Of course, you'll probably end up with diagonals where the mouse tested a dead-end. In your example, here's the output:

This is easy to fix. Just scan the entire maze for "." tiles, and check the tiles surrounding it in the four compass directions. If you get 2 "+"'s, add a "+" to that period tile.

I'm going to run this in my head a few times to see if I can spot any errors in my logic..

Thanks BlueCube. That seems to make sense. I'll give it a shot. If that doesn't work, I was thinking about using a depth-first search. Do you think that would work?

Make an array of ints from the map. Make walls -1, paths 0, and also store the coordinates of the start and the end. Mark the start point with a 1. Then loop, marking each 0 adjacent to a positive number with the next highest number untill the destination point gets written. After that, follow back the numbers in reverse order to find the shortest path.

Thanks WW and BlueCube.. I got it to work.