Word Search in Grid with Diagonal Moves

You are given a grid of characters with dimensions \(m \times n\) and a word. Your task is to determine whether the word exists in the grid. The word can be constructed by sequentially adjacent cells, where adjacent cells are those that are horizontally, vertically, or diagonally neighboring. Once a cell is used in the path, it cannot be used again.

The moves allowed from any position \((i,j)\) are in 8 directions: up, down, left, right, and the four diagonal directions. Formally, if you are at cell \((i,j)\), you may move to cell \((i+dx, j+dy)\) where \(dx, dy \in \{-1, 0, 1\}\) but not both zero.

Note: The search should be case-sensitive. The existence of the word means that there is a valid path in the grid that spells out the word exactly.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers \(m\) and \(n\), representing the number of rows and columns in the grid.
• The next \(m\) lines each contain a string of length \(n\), representing a row of the grid.
• The last line contains the target word to search for in the grid.

It is guaranteed that \(1 \leq m, n \leq 100\) and the word length is at least 1.

outputFormat

Output a single line to standard output (stdout) containing either true if the word exists in the grid or false otherwise.

3 4
abce
sfcs
adee
abcced

true