Given a two dimentional maze which only has one path from entrance to exit, develop an algorithm that discovers the no-dead-ends route from start to finish.
Use the always-turn-right rule but like Hansel & Gretel drop bread
crumbs as you go. Drop a bread crumb at the entrance to each
"room" (a room is a square in the maze), and at the exit (next to the
room where you're going next).
When you find a dead end, turn around & start picking up bread
crumbs, continuing to follow the turn-right rule. When you enter
a room if you find a bread crumb at that entrance, pick it up;
otherwise drop one. When you leave a room, if you find a bread
crumb at that exit, pick it up; otherwise drop one there.
This will leave a trail of bread crumbs, two crumbs in each room, that
defines the no-dead-ends route. The advantage of this technique
over the earlier posts, is that you don't have to back track. You
only travel through the maze once.
Edited on February 22, 2005, 4:46 am