Maze Solving using graph

Question

Hey i was in a local programming competition and they asked me this question which i could not do so please help me on this one.

Write a program that loads from a file the size of a maze and then the maze itself. To model the maze we use the character "S" that specifies the start cell, "." that specifies free cell, "#" is a wall and "F" is the final cell. Write a program that will find a path from the start cell to the final cell. You can think that in the maze there is a robot that obeys commands, so for the following maze the robot should receive the following commands: up, up, right, right, down, down.

maze 1 text file

5 5
#####
#...#
#.#.#
#S#T#
#####

maze 2 text file

4 5
#.#.#
#.#.#
#S#T#
#####

Write your program in general (the maze maximum input can be at most 200x200).

Help would be much appreciated. I am just a rising sophmore so if you could provide me the code then i could understand it and they do it again bymyself.

Answer 1

One way to find a path:

1. Have a queue of cells to check, and a count of steps for each cell from there to the destination.
2. Set the ending cell's count to 0, and add it to the queue.
3. While the queue is not empty:
   1. Get a cell from the queue.
   2. For each free neighbor cell, compare the current cell's count + 1 to the neighbor cell's count. If it's less, of if the neighbor cell doesn't have a count yet, set the neighbor cell's count to the current cell's count + 1, then add the neighbor cell to the queue.

Once the queue's empty, every free cell in the maze (that can be reached from the destination) will have the number of steps in the shortest path to the destination. If a cell doesn't have a count, there's no path from it to the destination.

If the start cell has a count,

1. Get the start cell's count.
2. Check each neighbor cell for a count of (count - 1). There will be one, and that's the next step in the path. Record the direction to that cell, and then get that cell, and if it's not the destination, repeat step 2 with that cell.

I'll leave it up to you to figure out how to load the maze. That's the easy part of all this.

Answer 2

In case you don't know what to search for: http://en.wikipedia.org/wiki/Pathfinding#Sample_algorithm and this contains a LOT more info: http://www.astrolog.org/labyrnth/algrithm.htm

Answer 3

The code is too much to write here, but the most common way of solving mazes is to set off in one direction, and at every right turn you can make, turn right.

This is guaranteed to work so long as the start and exit are in one of the four surrounding walls. For mazes that don't have their start and exit along the walls, it's an exercise in recursion.

See what you can come up with code-wise based off that as a starting point!

HTH, James