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.
