因此，我正在研究 BFS 算法來(lái)查找二維二元迷宮中的最短路徑，并以坐標(biāo)的形式打印路徑。代碼正在運(yùn)行，但肯定有什么地方有錯(cuò)誤?；旧?，迷宮坐標(biāo)有 true 或 false 值（其中墻壁為 false）。迷宮中的坐標(biāo)以名為 的自定義類的形式給出Pos。我的目標(biāo)是找到路徑，將點(diǎn)添加到列表中（以 Pos 的形式）并返回?cái)?shù)組列表ArrayList<Pos> path該代碼在另一個(gè)類中運(yùn)行，該類從文件中讀取迷宮.in，然后在所述迷宮上運(yùn)行我的算法。如果ArrayList<Pos> path返回 an 它將打印每個(gè)元素。如果不是，它只會(huì)打印“無(wú)法解決”。假設(shè)我有文件 test.in 并運(yùn)行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]通過(guò)查看輸出，算法似乎找到了最短路徑，但將每個(gè)坐標(biāo)打印兩次。此外，x 和 y 值會(huì)翻轉(zhuǎn)，并且起始坐標(biāo)會(huì)打印 3 次。非常感謝任何解決此問(wèn)題的幫助。
1 回答
慕標(biāo)5832272
TA貢獻(xiàn)1966條經(jīng)驗(yàn) 獲得超4個(gè)贊
您的問(wèn)題是path永遠(yuǎn)不會(huì)重置，只會(huì)添加。您需要以某種方式跟蹤 aPos或關(guān)卡的先前位置。
嘗試這個(gè)：
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;
添加回答
舉報(bào)
0/150
提交
取消