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

Question

我想写二维数组迷宫解算器，我明白了。但是，当 2d array map 有 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 algorithm，提供的解决方案不一定是到达目的地的最短路径。

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

另一个例子：

还有一个：

解决方案中的编号步骤表明 DFS 算法提供了通往目的地的漫长而曲折的路径。

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

Answer 2

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

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

My 2d maze solver doesn't work for multiple choice

java

algorithm

maze