我的数组可能看起来像这样:
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
提前一百万致谢!
你好乔纳斯
最佳答案
一个问题:您的test_connection
有点像flood fill algorithm , 但它只会向右和向下移动。您还需要修改函数以填充和向左填充。
它对第一种情况非常有效,因为仅当从左上角向右和向下移动时,“E”形状才能正确填充。但是当“E”被翻转时(你的第二种情况,递归调用不再到达“E”的水平条。
关于javascript - 在javascript 2d矩阵中查找连接的组件,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47209203/