2D矩阵中

2D矩阵中

关注
发信
关注(28)粉丝(399)

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

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

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数组代码段，因为我的问题很长。因此，请尝试使用您自己的error_array。

我希望有人可以解释如何修复我的代码：）


  编辑1：这是error_array的输出


javascript - 在JavaScript 2D矩阵中查找连接的组件-LMLPHP

预先感谢一百万！

问候乔纳斯

最佳答案

一个问题：您的test_connection有点像flood fill algorithm，但是它只能左右移动。您需要修改功能以将其填充到左侧。

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

关于javascript - 在JavaScript 2D矩阵中查找连接的组件，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47209203/

10-10 06:45
Powered by LMLPHP ©2024 2D矩阵中 0.044191