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

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;

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

标签： c++algorithmdynamic-programming

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;