檢測在二維數組模式的閉環

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], 
] 

我如何確定'1'的模式是閉環？我已經掙扎了幾天。我已經嘗試了遞歸循環找鄰居和文字，但是當你有一個更復雜的模式將無法正常工作，例如：

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

其中行和列是二維陣列大小

UPDATE

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

：

如果有至少一個閉環這將返回true

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

更新2 提取環路（S）：

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/

UPDATE 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