I am reading Adam Drozdek’s book on DSA, and in solving the mouse in maze problem, he is using stacks. But how would I (if i wanted) count the number of steps the rat takes ? Because according to his stack solution , false positive neighbors (ie. the neigbors that failed to reach destination) also get marked, and there is no backtracking which unmarks these cells. Pls help me. Pls.
EDIT: his algorithm
exitMaze () while currentCell is not exitCell mark currentCell as visited; push unvisited neighbors of currentCell onto the stack if stack is empty failure; else pop off a cell from the stack and make it currentCell success;
This way the maze will be filled with a path of X’s starting from Rat’s initial point to exit point. But it will also be filled with ‘X’s on the tried and failed paths. So how do i count the number of steps in the path ?
Source: Windows Questions C++