因此，我正在研究 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 次。非常感謝任何解決此問題的幫助。
1 回答
慕標5832272
TA貢獻1966條經驗 獲得超4個贊
您的問題是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;
添加回答
舉報
0/150
提交
取消