在 Java 的迷宫中追溯路径

Question

所以我有一个程序可以正确地解决迷宫问题，并将解决方案存储在一个多维整数数组 solvedMaze 中，如下所示：

指出开始和结束的位置：

我必须解决和追溯迷宫路径的代码如下：

public List<Location> solution() {
    int[][] solvedMaze = new int[height][width];
    Location current;

    PriorityQueue<Location> queue = new PriorityQueue<>(new Comparator<Location>() {
        @Override
        public int compare(Location a, Location b) {
            double distanceA = distance(start, a) / 1.5 + distance(a, end);
            double distanceB = distance(start, b) / 1.5 + distance(b, end);
            return Double.compare(distanceA, distanceB);
        }

        private double distance(Location first, Location second) {
            return Math.abs(first.i() - second.i()) + Math.abs(first.j() - second.j());
        }
    });

    queue.add(start);

    while ((current = queue.poll()) != null) {
        if (solvedMaze[current.i()][current.j()] != 0) {
            continue;
        }

        int mod = 1;

        for (Location next : new Location[]{
            current.south(), current.west(), current.north(), current.east()
        }) {
            if (isInMaze(next) && isClear(next)) {
                if (solvedMaze[next.i()][next.j()] == 0) {
                    queue.add(next);
                } else {
                    mod = Math.min(solvedMaze[next.i()][next.j()], mod);
                }
            }
        }

        solvedMaze[current.i()][current.j()] = mod;

        if (isFinal(current)) {
            break;
        }
    }

    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            System.out.print(solvedMaze[i][j]);
        }
        System.out.println();
    }

    if (solvedMaze[end.i()][end.j()] != 0) {
        List<Location> route = new ArrayList<>();
        Location temp = end;

        while (!temp.equals(start)) {
            route.add(temp);

            Location best = null;
            int bestNumber = solvedMaze[temp.i()][temp.j()];

            for (Location next : new Location[]{
                temp.north(), temp.south(), temp.west(), temp.east()
            }) {
                if (isInMaze(next) && solvedMaze[next.i()][next.j()] != 0) {
                    if (solvedMaze[next.i()][next.j()] < bestNumber) {
                        bestNumber = solvedMaze[next.i()][next.j()];
                        best = next;
                    }
                }
            }

            assert best != null;
            temp = best;
        }

        route.add(start);
        Collections.reverse(route);

        return route;
    } else {
        return null;
    }
}

其中 Location 是包含 x 和 y 坐标的 class，start 和 end 是位置。出于某种原因，我的输出总是 null，我不确定为什么。经过一些简单的print调试，我发现回溯逻辑中的solvedMaze[next.i()][next.j()] < bestNumber条件从未进入。方法有什么问题？有没有更好（更高效）的方法解决？

Answer 1

您显示的逻辑似乎依赖于 solvedMaze 上的 1 已被替换为 "shortest distance from start"，这就是为什么它在路径上从 End 到 Start 向后遍历更好的（又名降序）数字。

例如solvedMaze 应该是：

1  2  0 12 13 14
2  3  0 11  0 15
0  4  0 10  0  0
6  5  0  9  0  0
0  6  7  8  0  0
0  0  0  0  0  0

在 Java 的迷宫中追溯路径

Retracing a path through a maze in Java

java

arrays

queue

maze