Supposing you are in a labyrinth, but you have a map and know where you are, there are many algorithms that will find a way out, if there is one.

Now, imagine you are allowed to wreck walls and make holes in them, so as to pass through. If you wreck enough walls, you are certain to be able to leave the labyrinth!

The problem: find an algorithm that determines the MINIMUM number of walls that should be broken in order to escape. Of course, it should also determine WHICH walls to break!

A wall should only be broken if it leads to a section closer to the exit.  My algorithm works back from the exit to determine how far each section is. 

Label every wall that is in part of the maze that contains the exit with a one (indicating that if we had to break one wall from the other side it would be here) and label every floor with a zero (indicating that from within this part no walls need to be broken).

Label the floor in every unlabeled part of the maze that borders a wall marked one with a one and label every remaining wall in this section with a two.

Label every unlabeled floor bordering a two with a two and label every rmaining wall in the section with a three. 

Continue until you label the floor of the part where you are.  The label will tell you how many walls you need to break.  You should break a wall of the same number.

Posted by Jer on 2006-04-03 13:24:26