算法以匹配序列在给定的n * m个矩阵

Question

我有一个矩阵是n * m个维度的，我打算一组数字的匹配与给定的矩阵。如果图案落在矩阵的垂直或水平列中，则非常简单，但如果图案以对角线方式落下，我无法检测到它。 例如，如果我不得不匹配的给定模式[-1，-1，-1]在下面的矩阵

0 0 0 -1 0

0 0 -1 0 0

0 -1 0 0 0

1 0 -1 -1 -1

在上述情况下，我shud能够检测-1组中的对角线方式以及所述一个在th最后一行。

我还可以具有输入其中

-1 0 0 -1 0

0 -1 0 0 0

0 -1 -1 0 0

1 0 -1 -1 -1

在这种情况下，要检测从右到左的对角线，并且最后一行也是。 基本上，在一个给定的序列中，我必须能够检测到它的存在，这可能以垂直方式或水平或对角方式存在。

我的问题：该算法具有不管其是否水平，垂直或对角本检测“所有”的序列。另外，请记住矩阵尺寸是N * M，因此它可以是任何尺寸。

Answer 1

我会注意到，你可以（有点详尽）具有不同的步幅遍历所述n行由M列的矩阵（作为单个载体处理） - 1，M-1，M，M + 1。在每个步骤的每个步幅开始（直到该步幅将离开矢量的末尾），并查看是否有匹配。

这至少消除了具有用于水平，垂直四种不同的算法，并且两个对角线。

在算法秩序方面很丑陋，但 - 相当多的N-平方。你可以用一个循环来限定起始单元格的所有四种可能性，因此，一旦找到了起点，就检查四步，所以你应该能够检查所有的东西。 。一个基本穿过基质）

Answer 2

不管优化技术，这个问题的更宽泛的版本是这样：

您有元件的阵列，其中每个元素是一个数字，其相对于相对定位对彼此。

E.g.数字60,50,40,30的从左到右的列表看起来像（60,0,0）（50,1,0）（40,2,0）（30,3,0）。如果这是一个从上到下的列表，它将是（60,0,0）（50,0,1）（40,0,2）（30,0,3）。如果它是从左上角到右下角的对角线，它将是（60,0,0）（50,1,1）（40,2,2）（30,3,3）。

因此，以这种方式，问题已经变得更为通用： 您想要在矩阵内的通用坐标指定的方向中查找数字列表。然后

一般的算法是这样的：

For each configuration 
    For each coordinate of the matrix 
     For each element in the list and corresponding local coordinate 
      Add the local coordinate to the coordinate within the matrix 
      If the value at that coordinate in the matrix does not match go to next configuration 
    We found a match! Prosperity and happiness! 

魔鬼，像往常一样，在细节。具体而言，在这种情况下，您实际上并不想查看矩阵的所有坐标。你真正想要的是遍历所有的坐标，当添加到模式时会产生匹配的可能性，而不会超出矩阵。 （这样做的错误检查要少得多。）

这是一个简单的2D裁剪问题。在配置的相对定位值中查找最低的X和Y以及最高的X和Y.如果您使用的是基于零索引的矩阵，则需要起始坐标为-lowX,-lowY，最大坐标为matrixMaxX - 1 - highX,matrixMaxY - 1 - highY。

增加的好处是，你可以添加任何你想要的形状，而不只是上/下/左/右/四对角线。但这取决于你。

Answer 3

虽然这是一个老问题，但我希望我的回答可以帮助某人。

在一个井字棋项目上工作时，我试图推广一个解决方案，我认为它也可以解决您的问题。 此实现将寻找“行模式”（这意味着它仅适用于元素的序列上的水平/垂直/对角线。

function lookForCombinationsOnGrid(grid, ...args) { 
/* This function looks for a linear sequence of elements (x, o, undefined) 
on the grid. 
It returns an array of all beginning and ending coordinates (x, y) for 
the corresponding pattern. 
Inputs: 
- grid, a system of coordinates with an x-axis and an inverted y-axis. 
- elements can be any sort of built-in objects. 
*/ 

let sequence = []; 
sequence.push(args[0]); 
args.reduce(function (accumulator, currentValue, currentIndex, args) { 
    return sequence.push(currentValue); 
}); 
console.log("sequence =", sequence); 

let testedArr; 
// Look for this combination horizontally. 
let result1 = []; 
for (i = 0; i < grid.length; i++) { 
    for (j = 0; j <= grid[i].length - sequence.length; j++) { 
     testedArr = []; 
     for (k = 0; k < sequence.length; k++) { 
      testedArr.push(grid[i][j + k]); 
     } 
     if (testedArr.join() === sequence.join()) { 
      let start = [j, i]; 
      let end = [j + sequence.length - 1, i]; 
      result1.push([start, end]); 
     } 
    } 
} 
console.log("Found", result1.length, "results horizontally. "); 

// Look for this combination vertically. 
let result2 = []; 
for (i = 0; i < grid[0].length; i++) { 
    for (j = 0; j <= grid.length - sequence.length; j++) { 
     testedArr = []; 
     for (k = 0; k < sequence.length; k++) { 
      testedArr.push(grid[j + k][i]); 
     } 
     if (testedArr.join() === sequence.join()) { 
      let start = [i, j]; 
      let end = [i, j + sequence.length - 1]; 
      result2.push([start, end]); 
     } 
    } 
} 
console.log("Found", result2.length, "results vertically. "); 

// Look for this combination diagonally. 
let result3 = []; 
for (i = 0; i <= grid.length - sequence.length; i++) { 
    for (j = 0; j <= grid[i].length - sequence.length; j++) { 
     testedArr = []; 
     for (k = 0; k < sequence.length; k++) { 
      testedArr.push(grid[i + k][j + k]); 
     } 
     if (testedArr.join() === sequence.join()) { 
      let start = [j, i]; 
      let end = [j + sequence.length - 1, i + sequence.length - 1]; 
      result3.push([start, end]); 
     } 
    } 
} 
console.log("Found", result3.length, "results diagonally (left to right). "); 

// and diagonally the other way... 
let result4 = []; 
for (i = 0; i <= grid.length - sequence.length; i++) { // line i = 0 
    for (j = grid[i].length-1 ; j >= 0 + sequence.length-1; j--) { // column j = 1 
     testedArr = []; 
     for (k = 0; k < sequence.length; k++) { 
      testedArr.push(grid[i + k][j - k]); // + 1 line to i, -1 col to j 
     } 
     if (testedArr.join() === sequence.join()) { 
      let start = [j, i]; 
      let end = [j - sequence.length + 1, i + sequence.length - 1]; 
      result4.push([start, end]); 
     } 
    } 
} 
console.log("Found", result4.length, "results diagonally (right to left). "); 

let result = result1.concat(result2); 
result = result.concat(result3); 
result = result.concat(result4); 

return result; 
} 
grid = [[1, 1, 3], 
     [1, 1, 1], 
     [1, 1, 1], 
     [0, 1, 1]]; 
console.log(lookForCombinationsOnGrid(grid, 1, 1, 1, 0)); 

我希望这可以帮助别人。