Algorithm to match a sequence in a given n*m matrix

I have a matrix which is of n*m dimension and i intend to match a set of numbers with the given matrix. It is pretty straight forward if the pattern falls in the vertical or horizontal column of the matrix , but if the pattern falls in a diagonal fashion , i am unable to detect it. For example , if i had to match a given pattern of [-1 , -1 , -1 ] in the following matrix

0 0 0 -1 0

0 0 -1 0 0

0 -1 0 0 0

1 0 -1 -1 -1

In the above case i shud be able to detect the -1 group in the diagonal fashion as well as the one in the last row.

I can also have a input where in

-1 0 0 -1 0

0 -1 0 0 0

0 -1 -1 0 0

1 0 -1 -1 -1

In this case the diagonal from right to left is to be detected and the last row sequence too. Basically on a given sequence i must be able to detect its presence , which could be present in either a vertical way or horizontal or diagonal way.

My Problem: The algorithm has to detect the "all" sequences irrespective of whether its horizontal, vertical or diagonally present. Also 开发者_JAVA百科, do remember the matrix dimensions are N*M so it could be of any size.

---

I'll note that you could (somewhat exhaustively) iterate over the n row by m column matrix (treated as a single vector) with different strides -- 1, m-1, m, m+1. At each stride start at every position (up to the point where that stride would run off the end of the vector) and see if you have a match.

This at least eliminates having four different algorithms for the horizontal, vertical, and the two diagonals.

Pretty ugly in terms of algorithm order, though -- pretty much N-squared.

(Well, maybe not. You can qualify the starting cell with a single loop, for all four possibilities. So, once a start has been found, check the four strides. So you should be able to check for everything with one basic pass through the matrix.)

---

Regardless of optimization techniques, a more generic version of this problem is as such:

You have an array of elements where each element is a number and its relative positioning in relation to eachother.

E.g. a left-to-right list of the numbers 60,50,40,30 would look like (60,0,0) (50,1,0) (40,2,0) (30,3,0). If this were a top-to-bottom list, it would be (60,0,0) (50,0,1) (40,0,2) (30,0,3). If it were top-left to bottom-right diagonal, it would be (60,0,0) (50,1,1) (40,2,2) (30,3,3).

So, in this manner, the problem has been made more generic: You want to find a list of numbers in generic coordinate-specifiable orientations within a matrix.

The general algorithm then looks like this:

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!

The devil, as usual, is in the details. Specifically, in this case, you don't actually want to go over all of the coordinates of the matrix. What you REALLY want is to go over all coordinates that when added to the pattern will produce a possibility of a match while not going outside of the matrix. (That way there's far less error checking to do.)

This is a simple 2D clipping problem. Find your lowest X and Y and highest X and Y in the relative positioning values of a configuration. If you're using a zero-index based matrix, you want your starting coordinates to be -lowX, -lowY and your maximum coordinates to be matrixMaxX - 1 - highX, matrixMaxY - 1 - highY.

The added benefit is that you can add any shape you want, not just up/down/left/right/four diagonals. But it's up to you.

---

Though it's an old question, I hope my answer could help someone.

While working on a tic-tac-toe project, I tried to generalize a solution which I think could work for your question too. This implementation will look for "line patterns" (which means it only works for a sequence of elements on an horizontal/vertical/diagonal line.

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 ));

I hope this can help someone.