Word Search in a Matrix

You are given an m x n matrix of uppercase letters and a word. Your task is to determine whether the word exists in the matrix.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells include horizontal, vertical, and diagonal neighbors. More formally, if a cell is at position \((i,j)\), you can move to any cell at \((i+dx, j+dy)\) where \(dx,dy \in \{ -1, 0, 1 \}\) and not both are zero.

For example, if \(matrix[i][j]=L\) and you wish to match letter \(L'\) in the word, one of the eight directions must yield the complete word. Output YES if the word is found starting from any cell and following any one of the valid directions continuously, otherwise output NO.

Note: The search in one direction is continuous and does not allow changing the direction midway, nor wrapping around the matrix.

inputFormat

The input is given via standard input (stdin) and has the following format:

1. The first line contains two integers m and n (1 ≤ m, n ≤ 100), representing the number of rows and columns of the matrix.
2. The next m lines each contain a string of n uppercase letters (with no spaces) representing each row of the matrix.
3. The last line contains a word (a string of uppercase letters) that you need to search in the matrix.

outputFormat

Output a single line to standard output (stdout) containing YES if the word is found in the matrix following any of the 8 possible directions, otherwise output NO.

4 4
ABCD
EFGH
IJKL
MNOP
FGH

YES