Javascript 洪水填充算法陷入无限循环

Question

您好，我正在尝试在 javascript 中实现一个简单的洪水填充类型算法。基本上我有一个 3x3 板，我将其表示为一维数组。我想将每个“接触”的相等值的索引附加到一个单独的数组。因此，例如这个板:

[1][1][0]
[3][1][3]
[0][0][0]

将表示为一维数组，即 [1,1,0,3,1,3,0,0,0]。在 [1] 之一上运行 floodFill 后，它会产生一个类似于 [4, 1, 0] 的数组，因为这些是 1d 数组中接触的索引，它们具有相同的值。

代码如下:

var boardArray = new Array(1,1,0,3,1,3,0,0,0);
var comboArray = new Array();
function floodFill(n, diceVal) {
    if(boardArray[n] != diceVal) {
        return;
    }
    comboArray.push(n);

    if (n >0 && n < 8) {
    // right
    if(!(n%3==2)) {
        floodFill(n+1, diceVal);
    }

    // left
    if(!(n%3==0)) {
        floodFill(n-1, diceVal);
    }

    // up
    if(n>2) {
        floodFill(n-3, diceVal);
    }

    // down
    if(n<5) {
        floodFill(n+3, diceVal);
    }
    } else {
        return;
    }
}
floodFill(4,1);

谁能告诉我为什么会陷入无限循环？

Answer 1

在“向上”的情况下，第一次通过时，您将调用 floodFill(1,1);。该调用在其“关闭”情况下将调用 floodFill(4,1);，后者将很快调用 floodFill(1,1)

您已经在跟踪匹配的方 block - 唯一真正会造成麻烦的方 block 。只需确认您没有再次检查同一个方 block :

function floodFill(n, diceVal) {
  if(boardArray[n] != diceVal) {
    return;
  }

  // have we been here before?
  if (comboArray.indexOf(n) >= 0)
    return;

  comboArray.push(n);

  // ...
}