我认为我的 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或关卡的先前位置。尝试这个：&nbsp; &nbsp; while (!q.isEmpty()) {&nbsp; &nbsp; // Pop front node and process&nbsp; &nbsp; &nbsp; &nbsp; Node node = q.poll();&nbsp; &nbsp; &nbsp; &nbsp; currX = node.x;&nbsp; &nbsp; &nbsp; &nbsp; currY = node.y;&nbsp; &nbsp; &nbsp; &nbsp; int d = node.d;&nbsp; &nbsp; &nbsp; &nbsp; path.removeRange(d, path.size());&nbsp; &nbsp; &nbsp; &nbsp; path.add(new Pos(curX, curY));&nbsp; &nbsp; &nbsp; &nbsp; // If end is found, stop&nbsp; &nbsp; &nbsp; &nbsp; if (currX == endX && currY == endY)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min_d = d;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; // check all 4 directions from curr cell&nbsp; &nbsp; &nbsp; &nbsp; for (int k = 0; k < 4; k++)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (isValid(maze, visited, currX + r[k], currY + c[k]))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // mark as visited and add to path&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; visited[currX + r[k]][currY + c[k]] = true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; q.add(new Node(currX + r[k], currY + c[k], d + 1));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }更新：class Node {&nbsp; &nbsp; int x;&nbsp; &nbsp; int y;&nbsp; &nbsp; Node prev;&nbsp; &nbsp; Node(int x, int y, Node prev) {&nbsp; &nbsp; &nbsp; &nbsp; this.x = x;&nbsp; &nbsp; &nbsp; &nbsp; this.y = y;&nbsp; &nbsp; &nbsp; &nbsp; this.prev = prev;&nbsp; &nbsp; }};...&nbsp; &nbsp; while (!q.isEmpty()) {&nbsp; &nbsp; // Pop front node and process&nbsp; &nbsp; &nbsp; &nbsp; Node node = q.poll();&nbsp; &nbsp; &nbsp; &nbsp; currX = node.x;&nbsp; &nbsp; &nbsp; &nbsp; currY = node.y;&nbsp; &nbsp; &nbsp; &nbsp; // If end is found, stop&nbsp; &nbsp; &nbsp; &nbsp; if (currX == endX && currY == endY)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ArrayList<Pos> path = new ArrayList<>();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; do {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; path.add(0, new Pos(node.x,node.y));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node = node.prev;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } while (node != null);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return path;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; // check all 4 directions from curr cell&nbsp; &nbsp; &nbsp; &nbsp; for (int k = 0; k < 4; k++)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (isValid(maze, visited, currX + r[k], currY + c[k]))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // mark as visited and add to path&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; visited[currX + r[k]][currY + c[k]] = true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; q.add(new Node(currX + r[k], currY + c[k], node));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return null;