JS最大调用栈超过P5

Question

我正在尝试编写程序来计算 p5.js 中最大的颜色连接块。问题是，当我递归调用它给出的盒子邻居时 - "The maximum call stack exceed" 我知道错误的含义，但我不知道为什么会发生。这是我的代码：

class Box {
  constructor(id, x, y, w, h, col, colId) {
    this.id = id;
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
    this.col = col;
    this.colId = colId;
  }

  render() {
    fill(this.col);
    stroke(1);
    rect(this.x * this.w, this.y * this.w, this.w, this.h);
  }

  getNeighbour(visited, x, y) {
    if(x - 1 < 0 || x + 1 >= rows || y - 1 < 0 || y + 1 >= cols) {
      return -1; 
    }
    else {
      this.col = color(10,10,10);
      arr[x-1][y].getNeighbour(visited,x-1,y);
      arr[x+1][y].getNeighbour(visited,x+1,y);
      arr[x][y-1].getNeighbour(visited,x,y-1);
      arr[x][y+1].getNeighbour(visited,x,y+1);
    }
    if(!this.contains(this.id)) {
      visited.push(this.id); 
    }
    
    
    
  }
  
  contains() {
    for(let i = 0; i < visited.length; i++) {
      if(this.id == visited[i]) return true; 
    }
    return false;
  }
}

请告诉我问题出在哪里。我当时也试过做检查。首先是左边的邻居，效果很好。但是，当我也添加正确的时，会出现此错误。我想我已经满足了适当的默认情况，但实际情况可能有所不同。

Answer 1

当你从一个盒子开始时，它会递归到它左边、右边、上面和下面的盒子。这四个盒子也是如此。但是如果你在上面的盒子上并且它调用下面的盒子，你就回到了你开始的地方。如此反复，直到您的堆栈用完。

根据您要执行的操作，一个简单的解决方案是拉动 "contains" 检查，如果之前访问过该框则中止：

getNeighbour(visited, x, y) {
    if( isOutsideBounds(x,y) || visited.indexOf(this.id) > -1) {
      return -1; 
    }
    this.col = color(10,10,10);
    visited.push(this.id)
    arr[x-1][y].getNeighbour(visited,x-1,y);
    arr[x+1][y].getNeighbour(visited,x+1,y);
    arr[x][y-1].getNeighbour(visited,x,y-1);
    arr[x][y+1].getNeighbour(visited,x,y+1); 
}

此外，您的 contains() 函数似乎访问了 visited 数组，该数组不在函数的范围内。

Answer 2

而不是：

else {
  this.col = color(10,10,10);
  arr[x-1][y].getNeighbour(visited,x-1,y);
  arr[x+1][y].getNeighbour(visited,x+1,y);
  arr[x][y-1].getNeighbour(visited,x,y-1);
  arr[x][y+1].getNeighbour(visited,x,y+1);
}
if(!this.contains(this.id)) {
  visited.push(this.id); 
}

尝试：

else if(!this.contains(this.id)) {
  visited.push(this.id);
  this.col = color(10,10,10);
  arr[x-1][y].getNeighbour(visited,x-1,y);
  arr[x+1][y].getNeighbour(visited,x+1,y);
  arr[x][y-1].getNeighbour(visited,x,y-1);
  arr[x][y+1].getNeighbour(visited,x,y+1);
}

进一步：我不确定 this.contains 是否正确，也许可以尝试：visited.contains... ?

Answer 3

这是一种抽象方法。你可以拿一个岛计数器，数一数每个岛上的物品。

function check(array) {

    function test(array, i, j, value) {
        if (array[i] && array[i][j] === -1) {
            count[value] = (count[value] || 0) + 1;
            array[i][j] = value;
            test(array, i - 1, j, value);
            test(array, i + 1, j, value);
            test(array, i, j - 1, value);
            test(array, i, j + 1, value);
            return true;
        }
    }
    
    var value = 1,
        count = {};

    array.forEach(a=> a.forEach((b, i, bb) => bb[i] = -b));
    array.forEach((a, i, aa) => a.forEach((b, j) => test(aa, i, j, value) && value++));
    array.map(a => console.log(...a));
    return count;
}

console.log(check([[1, 0, 1], [1, 0, 0], [1, 1, 1]]));
console.log(check([[1, 0, 1], [0, 1, 0], [1, 0, 1]]));
console.log(check([[1, 0, 0, 1, 1], [1, 1, 1, 0, 0], [0, 0, 1, 0, 1], [0, 0, 1, 0, 1], [1, 1, 1, 0, 1]]));

.as-console-wrapper { max-height: 100% !important; top: 0; }

JS最大调用栈超过P5

JS maximum call stack exceeded P5

javascript

recursion

class

object

p5.js