算法以匹配序列在給定的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)); 

我希望這可以幫助別人。