检测二维阵列模式中的闭环

Question

假设您得到以下数组：

foo = [
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,1,1,1,1,1,0,0],
    [0,0,0,1,0,0,0,1,0,0],
    [0,0,0,1,0,0,0,1,0,0],
    [0,0,0,1,1,1,0,1,0,0],
    [0,0,0,0,0,1,0,1,0,0],
    [0,0,0,0,0,1,1,1,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
]

如何判断1s的形态是否为闭环？我已经为此苦苦挣扎了几天。我尝试了一个递归循环来查找邻居和单词，但是当你有一个更复杂的模式时它就不起作用了，例如：

foo = [
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,1,1,1,0,0,0,0],
    [0,0,0,1,0,1,0,0,0,0],
    [0,0,0,1,0,1,0,0,0,0],
    [0,0,0,1,1,1,1,1,0,0],
    [0,0,0,0,0,1,0,0,0,0],
    [0,0,0,0,0,1,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
]

有人有解决这个问题的神奇算法吗？ :(

Answer 1

正如 Dagrooms 所说，尝试找到只有一个相邻 1 的 1(s)。代码如下：

function isValid1(x,y){
  return (foo[x-1][y] + foo[x+1][y] + foo[x][y-1] + foo[x][y + 1])>1;
}

function validLoop(){
  for(var i = 0; i < rows; i++){
    for(var j = 0; j < columns; j++){
      if(foo[i][j] === 1 && !isValid1(i,j)) {
        return false;
      }
    }
  }
  return true;
}

其中行和列是二维数组大小。

更新

如果至少有一个闭环，这将 return 为真：

function numTouching1(x,y){
  return foo[x - 1][y] + foo[x + 1][y] + foo[x][y - 1] + foo[x][y + 1];
}

function validLoop(){
  var n = 0, x = 0; // x is current point's number of touching 1 and n is total
  for(var i = 0; i < rows; i++){
    for(var j = 0; j < columns; j++){
      if(foo[i][j] === 1) {
        x = numTouching1(i, j) - 2;
        if(x === -1 || x === 1 || x === 2){
          n += x;
        } 
      }
    }
  }
  return n > -1;
}

JSFiddle：https://jsfiddle.net/AdminXVII/b0f7th5d/

更新 2 提取循环：

function numTouching1(x,y){
  return foo[x - 1][y] + foo[x + 1][y] + foo[x][y - 1] + foo[x][y + 1];
}

function extractLoop(){
  for(var i = 0; i < rows; i++){
    for(var j = 0; j < columns; j++){
      if(foo[i][j] === 1 && numTouching1(i, j) === 1){
          foo[i][j] = 0;
          extractLoop();break;
      }
    }
  }
}

JSFiddle：https://jsfiddle.net/AdminXVII/b0f7th5d/7/

更新 3

如果有一个以上的循环，这是一种威胁，虽然一个循环会更慢。

function numTouching1(x, y) {
    return foo[x - 1][y] + foo[x + 1][y] + foo[x][y - 1] + foo[x][y + 1];
}

function extractLoop() {
    for (var i = 0; i < rows; i++) {
        for (var j = 0; j < columns; j++) {
            if (foo[i][j] === 1 && numTouching1(i, j) === 1) {
                foo[i][j] = 0;
                extractLoop(); break;
            }
        }
    }
}

function validLoop(){
  extractLoop();
  for(var i = 0; i < rows; i++){
    for(var j = 0; j < columns; j++){
      if(foo[i][j] === 1 && numTouching1(i,j) == 2) {
        return true;
      }
    }
  }
  return true;
}

JSFiddle：https://jsfiddle.net/AdminXVII/w7zcgpyL/

更新 4

更安全的numTouching1()方法：

function numTouching1(x, y) {
    return ((x > 0) ? foo[x - 1][y] : 0) + ((x < rows-1) ? foo[x + 1][y] : 0) + ((y > 0) ? foo[x][y - 1] : 0) + ((y < columns-1) ? foo[x][y + 1] : 0);
}

修改之前的JSFiddle

检测二维阵列模式中的闭环

Detecting closed loop in a 2D array pattern

javascript

arrays

html5-canvas

phaser-framework