The problem with BFS is that you have to remember how to get from where you are to every other point you have explored. Of course, the problem with a depth-first search is that in an unbounded maze, you may never reach a point even if it is very close to your starting point.
Don On Mar 3, 1:31 pm, Jammy <[email protected]> wrote: > BFS search the maze > > On Mar 2, 11:26 am, Don <[email protected]> wrote: > > > class coord > > { > > public: > > int x; > > int y; > > > }; > > > class SolveMaze > > { > > public: > > SolveMaze() { location.x = location.y = 0; } > > bool Explore(); > > private: > > list<coord> visited; > > coord location; > > > }; > > > bool Explore() > > { > > // Determine if we've already been here > > if (visited.found(location)) > > return false; > > > // Base case, we are at an exit > > if (HasLadder()) return true; > > > // Remember that we have been here > > visited.push(location); > > > // Try all four directions > > for(direction = 0; direction < 4; ++direction) > > { > > if (TryMove(direction)) > > { > > coord prev(location); // Copy current location > > > // Track our current location > > switch(direction) > > { > > case 0: --location.y; break; > > case 1: ++location.x; break; > > case 2: --location.x; break; > > case 3: ++location.y; break; > > } > > > // Explore from new location > > if (this->Explore()) return true; > > > TryMove(3-direction); // Assume 3-direction is opposite move of > > direction > > > // Back out location > > location = prev; > > } > > } > > > // Remove current location from list > > visited.pop(); > > > // No exit found > > return false; > > > } > > > On Mar 2, 9:05 am, bittu <[email protected]> wrote: > > > > You are in a maze(like a labyrinth), and you open your eyes so you > > > don't know your position. The maze has walls and you can move only in > > > up, right, left and down directions. You can escape the maze when you > > > find a ladder. > > > > The following API is given: > > > bool TryMove(direction) - returns true when you don't hit a wall; > > > bool HasLadder() - return true if you found the ladder. > > > > Write a method bool Explore() that returns true if you can escape the > > > maze, false otherwise. Also, provide test cases. > > > > A Good Explanation & Pseudo-code, Algorithmic discussion > > > needed..Object Oriented is Also Welcome > > > > Thanks & Regards > > > Shahsank > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
