我的 2d 迷宫求解器不适用于多项选择

Question

我想写二维数组迷宫求解器，我明白了。但是，当二维数组映射有 2 个或更多解决方案时，我的代码不起作用。public class Mapsolver {    private int tried = 2;    private int path = 3;    private int maze[][];    public Mapsolver(int maze[][], int destinationcolumn, int destinationrow, int locationcolumn, int locationrow) {        this.maze = maze;        traverse(locationrow, locationcolumn, destinationrow, destinationcolumn);    }    public boolean valid(int row, int column) {        boolean result = false;        if (row >= 0 && row < maze.length && column >= 0 && column < maze[row].length) {            if (maze[row][column] == 1) {                result = true;            }        }        return result;    }    public boolean traverse(int row, int column, int destrow, int destcolumn) {        boolean done = false;        if (valid(row, column)) {            maze[row][column] = tried;            if (row == destrow && column == destcolumn)                done = true;            else {                done = traverse(row + 1, column, destrow, destcolumn);                if (!done)                    done = traverse(row, column + 1, destrow, destcolumn);                if (!done)                    done = traverse(row - 1, column, destrow, destcolumn);                if (!done)                    done = traverse(row, column - 1, destrow, destcolumn);            }            if (done) {                maze[row][column] = path;            }        }        return done;    }    public String toString() {        String result = "\n";        for (int row = 0; row < maze.length; row++) {            for (int column = 0; column < maze[row].length; column++)                result += maze[row][column] + "";            result += "\n";        }        return result;    }}如果我们有一个解决方案，它绝对是正确的。但是，如果我们有 2 个或更多解决方案，则它标志着所有可能的解决方法。但是，我不想在打印时看到所有解决方案。正确的输出将是这些的一种解决方案。

Answer 1

您用于解决迷宫的算法是DFS 算法，提供的解决方案不一定是到目的地的最短路径。

递归的结束条件确保您只会收到一个解决方案。您认为的多个解决方案实际上是一个解决方案，如下面的打印示例所示，基于您的代码（10*10 网格，xx 是墙壁，目的地在 (6)(3)，每个迷宫单元格被封装在'|'中，访问的单元格是--'s）：

另一个例子：

还有一个：

解决方案中的编号步骤表明，DFS 算法提供了一条非常长且曲折的到达目的地的路径。

底线 - 你得到的解决方案比你想象的要长得多。

Answer 2

您可以为每个访问的顶点存储一个指向父顶点的指针，一旦到达目标顶点，您就停止搜索并将（反向）路径打印回起始顶点。但是在所谓的“完美”迷宫中，它只不过是一棵生成树，任何两个顶点之间总会有一条路径。