javascript - JavaScript 中的洪水填充算法 - 太多递归

Question

因此，我正在编写一个 Bejeweled 克隆代码，但我的 flood fill 函数有一个错误。我有一个 15 x 15 的矩阵，由不同颜色的珠宝组成，我尝试计算填充的瓷砖数量。

函数在这里:

function count(x, y, color) {

  if(matrix[x] && matrix[x][y]) {
    if(matrix[x][y].color != color)
      return;
    cnt++;
    count(x, y+1, color);
    count(x, y-1, color);
    count(x-1, y, color);
    count(x+1, y, color);
    console.log(cnt);
  }
}

怎么了？

Answer 1

看起来您的问题是您的函数无法区分已计数的方 block 和未计数的方 block 。所以相邻的方 block 会一直互相计数。

一个解决方案是处理您的网格副本，并修改访问过的方 block 的颜色，这样它们就不会被再次计算。或者，您可以向每个单元格添加一个 counted 属性，并在您对单元格进行计数时设置它，如果您尝试对一个已经被计数过的单元格进行计数则返回。然后确保在完成后重置 counted 属性。

类似于:

function count(x, y, color) {

  if(matrix[x] && matrix[x][y]) {
    if(matrix[x][y].color != color || matrix[x][y].counted)
      return;
    cnt++;
    matrix[x][y].counted = true;
    count(x, y+1, color);
    count(x, y-1, color);
    count(x-1, y, color);
    count(x+1, y, color);
    console.log(cnt);
  }
}