我认为我的 BFS 将所有有效坐标添加到列表中，而不仅仅是最短路径

Question

因此，我正在研究 BFS 算法来查找二维二元迷宫中的最短路径，并以坐标的形式打印路径。代码正在运行，但肯定有什么地方有错误。基本上，迷宫坐标有 true 或 false 值（其中墙壁为 false）。迷宫中的坐标以名为 的自定义类的形式给出Pos。我的目标是找到路径，将点添加到列表中（以 Pos 的形式）并返回数组列表ArrayList<Pos> path该代码在另一个类中运行，该类从文件中读取迷宫.in，然后在所述迷宫上运行我的算法。如果ArrayList<Pos> path返回 an 它将打印每个元素。如果不是，它只会打印“无法解决”。假设我有文件 test.in 并运行java driver < test.in：6 6#######A...##.##.##.##.##.B..#######我希望输出是：[1,1][2,1][3,1][4,1][4,2]但这就是我得到的：[1,1][1,1][1,1][1,2][2,1][1,3][3,1][1,4][4,1][2,4][4,2]通过查看输出，算法似乎找到了最短路径，但将每个坐标打印两次。此外，x 和 y 值会翻转，并且起始坐标会打印 3 次。非常感谢任何解决此问题的帮助。

Answer 1

您的问题是path永远不会重置，只会添加。您需要以某种方式跟踪 aPos或关卡的先前位置。

尝试这个：

    while (!q.isEmpty()) {

    // Pop front node and process

        Node node = q.poll();

        currX = node.x;

        currY = node.y;

        int d = node.d;

        path.removeRange(d, path.size());

        path.add(new Pos(curX, curY));

        // If end is found, stop

        if (currX == endX && currY == endY)

        {   

            min_d = d;

            break;

        }

        // check all 4 directions from curr cell

        for (int k = 0; k < 4; k++)

        {

            if (isValid(maze, visited, currX + r[k], currY + c[k]))

            {

                // mark as visited and add to path

                visited[currX + r[k]][currY + c[k]] = true;

                q.add(new Node(currX + r[k], currY + c[k], d + 1));

            }

        }

    }

更新：

class Node {

    int x;

    int y;

    Node prev;

    Node(int x, int y, Node prev) {

        this.x = x;

        this.y = y;

        this.prev = prev;

    }

};

...

    while (!q.isEmpty()) {

    // Pop front node and process

        Node node = q.poll();

        currX = node.x;

        currY = node.y;

        // If end is found, stop

        if (currX == endX && currY == endY)

        {   

            ArrayList<Pos> path = new ArrayList<>();

            do {

                path.add(0, new Pos(node.x,node.y));

                node = node.prev;

            } while (node != null);

            return path;

        }

        // check all 4 directions from curr cell

        for (int k = 0; k < 4; k++)

        {

            if (isValid(maze, visited, currX + r[k], currY + c[k]))

            {

                // mark as visited and add to path

                visited[currX + r[k]][currY + c[k]] = true;

                q.add(new Node(currX + r[k], currY + c[k], node));

            }

        }

    }

    return null;