DFS for a maze program I'm writing
Right now I am writing a maze program just for practice to take the Sun Programmer certification test. I am going to use DFS algorithm first, but I was wondering if there was a way to do DFS without using recursion. I am probably going to use recursion, because that seems more intuitive to me, but I was just wondering if there was a straight forward way of doing it without recursion.
Without recursion, I think you have to somehow keep this one universal data structure that remembers if you tried going right, left, up, or down yet, and to remember to try all those other possibilities before popping the stack. What do you guys think.
P.S. I posted this in the general forum before, and didn't really get a response, I am thinking maybe this forum would be better.
Of course you can do it without recursion, but it will not be so elegant :-).
The first idea is to simulate your recursion using a stack and introducing the values into it just as the normal recursive calls would do. But this would be not very useful because you would have to do a lot of work that would be avoided if normal recursion is used.
Another way to solve your problem could be use your "universal data structure". Every place in your universe would have the posibility of having 5 values:
0 - I have not tried to move to any direction
1 - I have tried to move to the left
2 - I have tried to move to the left and up
3 - I have tried to move to the left, up and right
4 - I have tried to move in the four directions.
It will also have a signal saying from where the place was first reached (from up, down, left or right).
So your algorithm would be something like:
while (this placce is not the exit)
if (current place has a state == 4) {
find a place where the state == 1, 2, 3
}
if (state == 0) {
try to move to the left
} else if (state == 1) {
try to move up
} else if (state == 2) {
try to move to the right
} else {
try to move down
}
}
you should take care only about your position (x, y) and take care that when you enter into a place where state is 0 you should set the signal which says from where the place was reached.
Once you found your destination you should only get back step by step (using your signals) till you reach the start place (so the path is construted from the end to the beggining).
Hope this helps.
Zerjillo
