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.
