Word Search in Grid

Given an \(m \times n\) grid of uppercase letters and a target word, determine whether the word exists in the grid. You can move from one letter to an adjacent one in any of the 8 possible directions (up, down, left, right, and the four diagonals). Each cell may be used at most once in forming the word.

Use depth-first search (DFS) or backtracking to explore all possible paths. Be cautious with boundary conditions and ensure that if a cell is used, it is not revisited in the same search path.

Input Constraints: The grid dimensions and word length are small, so a recursive solution is acceptable.

Mathematical Formulation:
Find a path in the grid \(G\) such that \[ G_{i_1,j_1} G_{i_2,j_2} \cdots G_{i_k,j_k} = W, \] where each consecutive pair \((i_t, j_t)\) and \((i_{t+1}, j_{t+1})\) are adjacent in one of the eight possible directions, and no cell is used more than once in the sequence.

inputFormat

The first line contains two integers \(m\) and \(n\), the number of rows and columns of the grid.

The next \(m\) lines each contain \(n\) space-separated uppercase letters representing the grid.

The last line contains the target word.

outputFormat

Output a single line containing "YES" if the word exists in the grid, and "NO" otherwise.

3 4
A B C E
S F C S
A D E E
ABCCED

YES