search word in matrix

Match word in matrix in any of 8 directions. From link.

[image from TH]

//matrix
 i---->m
j
|
|
n

- For every i,j square in matrix, try if the word matches.
- For any i,j square, the word[k] should match a[i,j] and any one of the neighboring 8 squares (excluding already matched squares) should match word[k+1].

indexs find(a, word):
    if a == null || a.length() == 0 || a[0].length() == 0:
        throw
    if word == null || word == "":
        throw
    m = a.length()
    n = a[0].length()
    for i = 0, i < m, i++:
        for j = 0, j < n, j++:
            if (a, i, j, m, n, word, squares, k: 0):
                return convert(squares, m)
    return convert(squares, m)

// return true if word is present starting with kth char in word till end
bool (a, i, j, m, n, word, squares, k):
    //this check needs to be before i, j check for a word ending in corner
    if k == word.length():
        return true
    if !((0 <= i < m) && (0 <= j < n)):
        return false
    if a[i][j] != word[k]:
        return false
    ijkey = flatten(i, j, m)
    if squares.has(ijkey):
        return false
    squares.add(ijkey)
    isnextmatch = 
           (a, i-1, j, m, n, word, squares, k+1)
        || (a, i+1, j, m, n, word, squares, k+1)
        || (a, i, j+1, m, n, word, squares, k+1)
        || (a, i, j-1, m, n, word, squares, k+1)
        || (a, i-1, j-1, m, n, word, squares, k+1)
        || (a, i-1, j+1, m, n, word, squares, k+1)
        || (a, i+1, j-1, m, n, word, squares, k+1)
        || (a, i+1, j+1, m, n, word, squares, k+1)
    if !isnextmatch:
        squares.removelast()
    return isnextmatch

// flattens i,j to an int
int flatten(i, j, m):
    return j*m + i

// unflattens int to i,j
int, int unflatten(x, m):
    return x/m, x%m

convert(squares, m):
    for x in squares:
        yield unflatten(x, m)

index:
    i, j

[Hat tip to SM, TH]