迷宫中的鼠标 - 堆栈（但也计算步数）

Question

我正在阅读 Adam Drozdek 关于 DSA 的书，在解决迷宫中的鼠标问题时，他使用了堆栈。但是我怎么（如果我想的话）计算老鼠走的步数呢？因为根据他的堆栈解决方案，误报邻居（即未能到达目的地的邻居）也会被标记，并且没有取消标记这些单元格的回溯。请帮助我。请

编辑：他的算法

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;

这样迷宫将充满从 Rat 的初始点到出口点的 X 路径。但它也会在尝试过的和失败的路径上充满“X”。那么我该如何计算路径中的步数？

Answer 1

对算法稍作改动，最后剩下的是堆栈中的路径：

exitMaze ()
    push start cell on the stack
    while stack is not empty
        let currentCell = top cell on the stack
        mark currentCell as visited; //it might already be marked, but that's OK
        if currentCell is exitCell
            success. Path is on the stack;
        else if currentCell has an unvisited neighbor
            push an unvisited neighbor on the stack
        else
            pop a cell off the stack
    failure;

迷宫中的鼠标 - 堆栈（但也计算步数）

Mouse in Maze - Stacks (but count steps also)

c++

algorithm

dynamic-programming