JavaScript中的填充算法-过多的递归 [英] Flood fill algorithm in JavaScript - too much recursion

问题描述

因此，我正在编码宝石迷阵克隆，并且洪水填充函数出错。我有一个15 x 15的不同颜色的珠宝矩阵，我尝试计算充满洪水的瓷砖数量。

So, I'm coding a Bejeweled clone and I have an error in my flood fill function. I have a 15 x 15 matrix of jewels of different color and I try to count the number of tiles with flood-fill.

功能在这里：

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

怎么了？

推荐答案

看来，您的问题是您的函数无法区分已计数的平方和未计数的平方。因此，相邻的正方形将继续相互计数。

It looks like your problem is that your function isn't distinguishing between squares that have been counted and squares that haven't. So adjacent squares will keep counting each other.

一种解决方案是在网格的副本上进行工作，并修改已访问正方形的颜色，以免再次计数。另外，您可以向每个单元格添加一个 counted 属性，并在对单元格进行计数时进行设置，如果要对已经计数的单元格进行计数，则返回该属性。然后，只需确保完成操作后重置 个属性即可。

One solution is to work off of a copy of your grid, and modify the color of the visited squares so they won't get counted again. Alternatively, you could add a counted property to each cell, and set it when you count the cell, and return if you're trying to count a cell that's already been counted. Then just make sure to reset the counted properties once you're done.

类似的事情：

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

这篇关于JavaScript中的填充算法-过多的递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！