javascript - 查找一个二维数组在另一个二维数组中出现的所有位置

Question

在 JavaScript 中，我试图找到这个 2D 整数数组的所有匹配坐标:

在此二维整数数组内，计算重叠子数组:

每个图像代表一个 2D JavaScript 整数数组，黑色像素对应于 1，黄色像素对应于 0，但我是这样描述数组的他们会更容易可视化。

那么我怎样才能找到数组 的所有匹配项？数组内 ？

这是我正在尝试实现的功能:

findAllMatchesOfOne2DArrayInsideAnother2DArray(containedArray, containingArray){
    //find all matching coordinates of containedArray inside containingArray, and return a 2D array of coordinates
}

Answer 1

Here is a way获取另一个 2D 数组中任何给定 2D 数组的所有出现情况。假设所有子数组都具有相同的维度(与 [[1,0,0],[1,0]] 不同)。

var x = [[0,1,0,0,0,0,0],
        [1,1,1,0,0,1,0],
        [0,1,0,0,1,1,1],
        [0,0,0,0,0,1,0],
        [0,0,1,0,0,0,0],
        [0,1,1,1,0,0,0],
        [0,0,1,0,0,0,0]];

var y = [[0,1,0],[1,1,1],[0,1,0]];

var res = [];
for (var i = 0; i < x.length - y.length + 1; i++) {
    for (var k = 0; k < x[0].length - y[0].length + 1; k++) {
        var count = 0;
        for (var l = 0; l < y.length; l++) {
             for (var m = 0; m < y[l].length; m++) {
                count += Math.abs(y[l][m] - x[i + l][k + m]);
            }       
        }
        if (count === 0) {
            res.push([i, k]);
        }

    }
}

数组res将包含每场比赛左上角的“坐标”。我相信您会找到性能更好的算法，但这个算法似乎有效:)