时间戳

首页 > 解决方案 > 如何解决可视化算法的问题

javascript - 如何解决可视化算法的问题

问题描述

我想实现一个问题，我们在迷宫中找到从 (0,0) 单元格到 (m-1,n-1) 单元格的路径，中间有一些障碍。
我已经使用递归回溯算法来解决这个问题，我只是想进行某种可视化，在其中我们可以看到我们在迷宫中旅行时路径是如何被采用的。我在这里
看到了这个问题

现在我已经使用javascript实现了它，我将我们正在访问的单元格着色为蓝色，然后如果我们回溯，则再次删除颜色，但一切都发生得非常快，因为我们看不到任何事情发生，所以我尝试使用sleep()函数来延迟但我认为我没有正确使用它们，因为任何随机模式都没有显示出它所采用的正确路径。

如果有人可以帮助我解决它，那将是一个很大的帮助。你可以在这里
检查我的问题

我寻找路径的算法是：

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);
  })
}

标签： javascriptalgorithmrecursionasync-awaitbacktracking

解决方案

您忘记了等待递归调用。

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");

在 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);
};

在 CodePen 上实时查看

推荐阅读