Mouse in Maze – Stacks (but count steps also)

  algorithm, c++, dynamic-programming

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++

LEAVE A COMMENT