quazyG
BAN USERI have solved it using non recursive DFS. The solution cannot be recursive. Unlike recursive function, where exiting the function retains its previous value, the robot cannot retain its previous value when going out of recursion. It must be told explicitly to turn in the opposite direction. So instead of recursion I used a stack for the angles of the robot.
class MazeWalker {
int mAngle;
std::stack<int> s;
Maze &mMaze;
public:
MazeWalker(Maze &maze): mAngle(0), mMaze(maze) {
}
void traverse(bool stopOnFlag);
private:
int left() { mAngle = (mAngle - 90) % 360; return 270; }
int forward() { mAngle = 0; return 0; }
int right() { mAngle = (mAngle + 90) % 360; return 90; }
int reverse(int angle) { mAngle = (360 - angle) % 360; return mAngle; }
bool goLeft() {
}
};
#define MAZE_WALKER_MOVE(f) \
mMaze.turn(f); \
if (!mMaze.wall()) { \
s.push(mAngle); \
mMaze.move(); \
continue; \
}
void MazeWalker::traverse(bool stopOnFlag) {
bool stop = false;
int step = 1;
while (!stop) {
cout << "Current step: " << step++ << " ";
mMaze.printCurrentCell();
if (stopOnFlag && mMaze.isFlag())
{
cout << "Found flag: ";
mMaze.printCurrentCell();
cout << endl;
return;
}
if (mMaze.isBreadcrumb()) {
if (s.empty())
return;
int angle = s.top();
s.pop();
mMaze.turn(angle);
mMaze.move();
continue;
}
MAZE_WALKER_MOVE(left())
MAZE_WALKER_MOVE(right())
MAZE_WALKER_MOVE(right())
mMaze.putBreadcrumb();
}
};
/*
*
*/
int main(int argc, char** argv) {
Maze m(5);
m.init();
m.print();
MazeWalker mw(m);
mw.traverse(true);
return 0;
}
I don't know if it's the fastest way a round but it's quite fast (usually below 10 steps)
I think it's called the Newton Raphson method.
- quazyG November 18, 2015