我想提出一个问题,我们在一个迷宫中找到从(0,0)单元到(m-1,n-1)单元的路径,中间有一些障碍。
我使用了递归回溯算法来解决该问题,我只想进行某种形式的可视化处理,从而可以看到在迷宫中旅行时如何采用该路径。
我看到了这个问题here
现在,我已经使用javascript实现了它,然后我将访问的单元格着色为蓝色,如果我们回溯,则再次删除颜色,但是一切都进行得非常快,因为我们看不到任何情况,所以我尝试使用sleep()
函数延迟,但是我认为我没有正确使用它们,因为任何随机模式都显示出它所采用的路径不正确。
如果有人可以帮助我解决问题,那将是很大的帮助。
你可以检查我的问题here
我寻找路径的算法是:
let getMazePath = async (maze, r, c, ans) => {
if (
r < 0 ||
c < 0 ||
r >= maze.length ||
c >= maze[0].length ||
maze[r][c] == 1 ||
visited[r][c] == 1
)
return;
if (r == maze.length - 1 && c == maze[0].length - 1) {
document.getElementById("path-display").innerHTML =
"Path is: '" + ans + "'";
console.log("Path is: '" + ans + "'");
return;
}
let currSq = document.getElementById(r + "_" + c);
currSq.classList.add("visited-square");
await sleep(1000);
visited[r][c] = 1;
getMazePath(maze, r - 1, c, ans + "t");
getMazePath(maze, r, c - 1, ans + "l");
getMazePath(maze, r + 1, c, ans + "d");
getMazePath(maze, r, c + 1, ans + "r");
visited[r][c] = 0;
currSq.classList.remove("visited-square");
await sleep(1000);
};
function sleep(ms){
return new Promise((resolve) => {
setTimeout(resolve, ms);
})
}
最佳答案
您忘记了等待递归调用。
通过在getMazePath
调用之前添加await
来解决此问题:
await getMazePath(maze, r - 1, c, ans + "t");
await getMazePath(maze, r, c - 1, ans + "l");
await getMazePath(maze, r + 1, c, ans + "d");
await getMazePath(maze, r, c + 1, ans + "r");
现场观看on CodePen当它找到路径时,您可能还想停止它。
为此,请返回答案并进行检查:
let getMazePath = async (maze, r, c, ans) => {
if (
r < 0 ||
c < 0 ||
r >= maze.length ||
c >= maze[0].length ||
maze[r][c] == 1 ||
visited[r][c] == 1
)
return;
if (r == maze.length - 1 && c == maze[0].length - 1) {
document.getElementById("path-display").innerHTML =
"Path is: '" + ans + "'";
console.log("Path is: '" + ans + "'");
return ans;
// ^^^
}
let currSq = document.getElementById(r + "_" + c);
currSq.classList.add("visited-square");
await sleep(1000);
visited[r][c] = 1;
{
const res = await getMazePath(maze, r - 1, c, ans + "t");
if(res) return res
}
{
const res = await getMazePath(maze, r, c - 1, ans + "l");
if(res) return res
}
{
const res = await getMazePath(maze, r + 1, c, ans + "d");
if(res) return res
}
{
const res = await getMazePath(maze, r, c + 1, ans + "r");
if(res) return res
}
visited[r][c] = 0;
currSq.classList.remove("visited-square");
await sleep(1000);
};
现场观看on CodePen