Can somebody help with my DFS algorithm...just pseudocode
Ok, if you've read my other posts, you know I am having some DFS alrogithm problems. I would like to go over my algorithm in pseudocode and see if I am screwing anything up. If you want to see the whole code, it is in my previous post. http://forum.java.sun.com/thread.jsp?forum=426&thread=310779
So I have a 2D array as my maze. My algorithm basically uses recursion and I all I do is basically I have pattern of movement, I check to see if I can move, right, then left, then up, then down. If I can move in any of those directions from my current position, I will push that move (or rather that cell) onto the top of the stack, and make my current cell that new cell now, and call the DFS algorithm again. When I push it onto the top of the stack, I also set the cell to visited, so that if I looped back around, I wouldn't check that cell again.
Now if let say I hit a cell, where I have nowhere to go anymore, I will pop the stack (and return false, but that is somewhat less consequential). I guess my big question is now this. when I pop the stack should I set that cell to unvisited?My reasoning for not ever setting something to unvisited, is because this: If I was at cell X, regardless of what my past was, and I was not able to find a solution from that point on, I should never venture to that point again, because that point will only lead me to a deadend eventually. So even if I went from Cell A->X and hit a dead end, but changed my path so that I went from B->G->X, it would eventually lead me to the same dead end (since DFS will find any solution, from any givent point). The reason I am not sure about this, is because when I first learned about this algorithm, I don't remember ever just leaving the cell variable as unvisited. It seems right to me now, and it seems like it makes some impossible calculations possible, but I am not sure, so I would like to get some advice. Thank you.
