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:

10 # # # # # # # # # # # . # M . . # . . # # . # # . # # # . # # . . . . . . . . # # # # # . # . # # # # . . . . # . # C # # # # # # # . # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # #

Sample Output:

# # # # # # # # # # # . # M + . # . . # # . # # + # # # . # # . . . + + + . . # # # # # . # + # # # # . . . . # + # C # # # # # # # + # + # # . # . . . + # + # # . . . # . + + + # # # # # # # # # # #

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

"Feel" the wall to the left of the mouse, depending on his direction IF (WallIsThere == false) { Rotate Counter-Clockwise Move Forward } ELSE { Check in front of the mouse IF (WallInFront == false) { Move Forward } ELSE { Rotate Couter-Clockwise } }

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:

# # # # # # # # # # # . # M + . # . . # # . # # + # # # . # # . . . + + . . . # # # # # . # + # # # # . . . . # + # C # # # # # # # + # + # # . # . . . + # + # # . . . # . + + + # # # # # # # # # # #

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.

# # # # # # # # # # # . # 1 . . # . . # # . # # . # # # . # # . . . . . . . . # # # # # . # . # # # # . . . . # . # . # # # # # # # . # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # . # 1 2 . # . . # # . # # . # # # . # # . . . . . . . . # # # # # . # . # # # # . . . . # . # . # # # # # # # . # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # . # 1 2 3 # . . # # . # # 3 # # # . # # . . . . . . . . # # # # # . # . # # # # . . . . # . # . # # # # # # # . # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # . # 1 2 3 # . . # # . # # 3 # # # . # # . . . 4 . . . . # # # # # . # . # # # # . . . . # . # . # # # # # # # . # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # . # 1 2 3 # . . # # . # # 3 # # # . # # . . 5 4 5 . . . # # # # # 5 # . # # # # . . . . # . # . # # # # # # # . # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # . # 1 2 3 # . . # # . # # 3 # # # . # # 7 6 5 4 5 6 7 . # # # # # 5 # 7 # # # # . . 7 6 # . # . # # # # # # # . # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # . # 1 2 3 # . . # # 8 # # 3 # # # . # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # . 8 7 6 # 8 # . # # # # # # # . # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # . . # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # . # # # # # # # 9 # . # # . # . . . . # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # . A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # . # # # # # # # 9 # . # # . # . . . A # . # # . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # . # # # # # # # 9 # . # # . # . . B A # . # # . . . # . B . . # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # . # # # # # # # 9 # . # # . # . C B A # . # # . . . # C B C . # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # . # # # # # # # 9 # . # # . # D C B A # . # # . . . # C B C D # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # . # # # # # # # 9 # . # # . # D C B A # E # # . . E # C B C D # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # . # # # # # # # 9 # F # # . # D C B A # E # # . F E # C B C D # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 #10 # # # # # # # 9 # F # # . # D C B A # E # #10 F E # C B C D # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # + # # # # # # # 9 # F # # . # D C B A # E # #10 F E # C B C D # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # + # # # # # # # 9 # + # # . # D C B A # E # #10 F E # C B C D # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # + # # # # # # # 9 # + # # . # D C B A # + # #10 F E # C B C D # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # + # # # # # # # 9 # + # # . # D C B A # + # #10 F E # C B C + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # + # # # # # # # 9 # + # # . # D C B A # + # #10 F E # C B + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # + # # # # # # # 9 # + # # . # D C B A # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # + # # # # # # # 9 # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # 8 # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # 7 # # # # 9 8 7 6 # + # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 6 7 8 # # # # # 5 # + # # # # 9 8 7 6 # + # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 5 + 7 8 # # # # # 5 # + # # # # 9 8 7 6 # + # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 4 + + 7 8 # # # # # 5 # + # # # # 9 8 7 6 # + # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # 3 # # # 9 # # 7 6 5 + + + 7 8 # # # # # 5 # + # # # # 9 8 7 6 # + # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 2 3 # B A # # 8 # # + # # # 9 # # 7 6 5 + + + 7 8 # # # # # 5 # + # # # # 9 8 7 6 # + # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # 1 + 3 # B A # # 8 # # + # # # 9 # # 7 6 5 + + + 7 8 # # # # # 5 # + # # # # 9 8 7 6 # + # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # 9 # + + 3 # B A # # 8 # # + # # # 9 # # 7 6 5 + + + 7 8 # # # # # 5 # + # # # # 9 8 7 6 # + # + # # # # # # # + # + # # . # D C B + # + # #10 F E # C + + + # # # # # # # # # # # # # # # # # # # # # # . # M + . # . . # # . # # + # # # . # # . . . + + + . . # # # # # . # + # # # # . . . . # + # C # # # # # # # + # + # # . # . . . + # + # # . . . # . + + + # # # # # # # # # # #

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