javascript - 在javascript 2d矩阵中查找连接的组件

Question

我的数组可能看起来像这样:

var array = [
    [1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    [0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    [0,0,1,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,0,0,0,0,0,0,0,0,0,0,0,0]
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    [0,0,0,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,1,1,0,0,0,0,0,0,0]
    [0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0]
    [0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0]
    [0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0]
    [0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0]
    [0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0]
    [0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0]
    [0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0]
    [0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0]
    [0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0]
    [0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,1,0,0,0]
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,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,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
]

我想在这个 2d 矩阵中找到所有连接的组件，比如中间的“E”字符，左上角的(我们称之为 SQUARE)和右下角的另一个“正方形”，用不同的数字标记它们以获得这样的结果:

var result = [
        [1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
        [0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
        [0,0,1,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,0,0,0,0,0,0,0,0,0,0,0,0]
        [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
        [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
        [0,0,0,0,0,0,2,2,2,2,2,2,2,0,0,0,0,0,0,0]
        [0,0,0,0,0,0,2,2,2,2,2,2,2,0,0,0,0,0,0,0]
        [0,0,0,0,0,0,2,2,0,0,0,0,0,0,0,0,0,0,0,0]
        [0,0,0,0,0,0,2,2,0,0,0,0,0,0,0,0,0,0,0,0]
        [0,0,0,0,0,0,2,2,0,0,0,0,0,0,0,0,0,0,0,0]
        [0,0,0,0,0,0,2,2,2,2,2,2,2,0,0,0,0,0,0,0]
        [0,0,0,0,0,0,2,2,0,0,0,0,0,0,0,0,0,0,0,0]
        [0,0,0,0,0,0,2,2,0,0,0,0,0,0,0,0,0,0,0,0]
        [0,0,0,0,0,0,2,2,0,0,0,0,0,0,0,0,0,0,0,0]
        [0,0,0,0,0,0,2,2,2,2,2,2,2,0,0,0,0,0,0,0]
        [0,0,0,0,0,0,2,2,2,2,2,2,2,0,0,0,3,0,0,0]
        [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,3,0,0]
        [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,3,3,0,0]
        [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    ]

我的代码绝对运行良好，如下所示:

var array = [
        [1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
        [0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
        [0,0,1,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,0,0,0,0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
        [0,0,0,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,1,1,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,1,0,0,0],
        [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,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,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
      ]
      
      
      
      

function find_connected_components(array) {
	var default_value=1;
	function test_connection(array, i, j, value) {
	    if (array[i] && array[i][j] === -1) {
	        array[i][j] = value;
	        test_connection(array, i + 1, j, value);
	        test_connection(array, i, j + 1, value);
	        return true;
	    }
	}
	array.forEach(function (a) {
	    a.forEach(function (b, i, bb) {bb[i] = -b;});
	});
	array.forEach(function (a, i, aa) {
	    a.forEach(function (b, j, bb) {test_connection(aa, i, j, default_value) && default_value++;});
	})
	console.log(array.map(a => [a.join('')]).map(a => [a.join('')]))
}


find_connected_components(array)      

但是-现在我的错误出现了，直到我从上面旋转我的数组。所以它看起来像这样:

var error_array = [
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,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,0,0,0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,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,1,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,1,1,1,1,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,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,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,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0],  
]

上面error_array的结果是完全错误的，我不知道如何解决这个问题。

PS:我没有编辑错误数组代码片段，因为我的问题太长了。请尝试自己的 error_array。

我希望有人能解释如何修复我的代码:)

Edit 1 : This is the output for the error_array

提前一百万致谢!

你好乔纳斯

Answer 1

一个问题:您的test_connection 有点像flood fill algorithm , 但它只会向右和向下移动。您还需要修改函数以填充和向左填充。

它对第一种情况非常有效，因为仅当从左上角向右和向下移动时，“E”形状才能正确填充。但是当“E”被翻转时(你的第二种情况，递归调用不再到达“E”的水平条。