检测2D阵列模式中的闭环

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(s)只有一个相邻1.代码如下:

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

其中行和列是2d数组大小.

UPDATE

如果至少有一个闭环,这将返回true:

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