迷宫不循环的 BFS 算法 - Javascript

Question

我正在尝试使用 BFS 算法来解决迷宫问题，我在一个数组中表示该迷宫，其中所有元素都以 999 开头，但中心（目标）为 0。我试图让代码从 0 开始并分支四种方式（北/南/东/西），如果数字大于父级，则将父级编号加 1。初始循环应该在中间有一个 0，四个相邻单元格应该从 999 更新为 1。这应该循环直到算法到达位置 0,0。不幸的是，我似乎无法让循环运行——我可以将前四个元素更新为 1，然后它就停止了。我认为这与我的队列如何/没有被拾取为下一个循环的 (y,x) 输入有关，但我似乎无法改变这一点。这是一项任务，因此不是在寻找解决方案，而是在帮助我了解我在循环中缺少什么方面的任何帮助将不胜感激。我已经在下面显示了数组代码 (mazeD) 和 BFS/flood 代码

// maze array showing numerical distance

let mazeD = [];

for (let y = 0; y < 10; y++) {

  let row = [];

  for (let x = 0; x < 10; x++) {

    row[x] = 999;

  }

  mazeD[y] = row;

}

mazeD[5][5] = 0;

// BFS function

function flood(x, y, d) {

  let queue = []

  queue.push([y, x]);

  while (queue.length > 0) {

    queue.shift();

    let fillArr = [

      [+y - 1, +x],

      [+y, +x - 1],

      [+y, +x + 1],

      [+y + 1, +x],

    ];

    if ((x < 10) && (y < 10)) {

      d++;

      for (let [yy, xx] of fillArr) {

      if (mazeD[yy][xx] > d) {

        queue.push([yy, xx]);

        mazeD[yy][xx] = d;

        console.log("queue =" +queue)

      }

    } 

  }

 }

}

flood(5, 5, 0);

console.log(mazeD);

Answer 1

就像这样：let mazeD = [];for (let y = 0; y < 10; y++) {&nbsp; let row = [];&nbsp; for (let x = 0; x < 10; x++) {&nbsp; &nbsp; row[x] = 999;&nbsp; }&nbsp; mazeD[y] = row;}mazeD[5][5] = 0;// BFS functionfunction flood(x, y, d) {&nbsp; let queue = [];&nbsp; let i = 0;&nbsp; queue.push([y, x]);&nbsp; while (i < queue.length) {&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; [x,y] = queue[i,i];&nbsp; &nbsp; let fillArr = [&nbsp; &nbsp; &nbsp; [+y - 1, +x],&nbsp; &nbsp; &nbsp; [+y, +x - 1],&nbsp; &nbsp; &nbsp; [+y, +x + 1],&nbsp; &nbsp; &nbsp; [+y + 1, +x],&nbsp; &nbsp; ];&nbsp; &nbsp; if ((x < 10) && (y < 10) && x >=0 && y>=0)&nbsp;&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; for (let [yy, xx] of fillArr)&nbsp;&nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; if(yy >=0 && yy < 10 && xx>=0 && xx<10)&nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (mazeD[yy][xx] == 999)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; queue.push([yy, xx]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; mazeD[yy][xx] = mazeD[y][x]+1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; console.log(xx,yy,mazeD[y][x]+1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(xx == 0 && yy == 0){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; }&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;}&nbsp; &nbsp;i++;&nbsp; }}flood(5, 5, 0);console.log(mazeD);

Answer 2

我认为您可能在这一行中遇到问题：queue.shift()似乎您永远不会读取存储在队列中的值，因此循环中的坐标永远不会更新，这意味着您总是在检查相同的位置。您可能希望将 的值赋给queue.shift()一个变量并使用这些坐标继续搜索。