Need a little help

[Demosthenes]

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 #
# # # # # # + # + #
# . # . . . + # + #
# . . . # . + + + #
# # # # # # # # # #

[BlueCube]

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..

[Demosthenes]

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?

[WetWired]

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 #
# # # # # # + # + #
# . # . . . + # + #
# . . . # . + + + #
# # # # # # # # # #

[Demosthenes]

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