Grid Search in a Matrix

Given a grid of characters and a target word, determine if the word can be found in the grid by sequentially adjacent letters. Letters can be adjacent in any of the 8 possible directions (horizontal, vertical, and diagonal). The same cell cannot be used more than once in the search path.

Formally, given a grid \(A\) of dimensions \(r \times c\) and a string \(S\) of length \(L\), check whether there exists a sequence of coordinates \((i_1, j_1), (i_2, j_2), \dots, (i_L, j_L)\) such that \(A[i_k][j_k] = S[k-1]\) for all \(1 \le k \le L\) and each consecutive pair of coordinates is adjacent (in one of the 8 possible directions). Use \(\LaTeX\) formatting for any formulas.

inputFormat

The first line contains two space-separated integers \(r\) and \(c\), representing the number of rows and columns, respectively.

The next \(r\) lines each contain a string of length \(c\) representing a row of the grid.

The last line contains the target word to search for in the grid.

outputFormat

Output true if the word exists in the grid following the allowed movements; otherwise, output false.

3 4
abce
sfcs
adee
abcced

true