Word Search in Grid

You are given a grid of characters of dimensions \( R \times C \), and a word. Your task is to determine whether the given word exists in the grid. You can start from any cell that matches the first letter of the word and then move in any of the 8 possible directions (up, down, left, right, and the 4 diagonal directions). When moving to the next letter, you cannot use the same cell more than once on the current search path.

The 8 possible directions can be represented by the following \( (dx, dy) \) pairs: \[ (0, 1),\ (0, -1),\ (1, 0),\ (-1, 0),\ (1, 1),\ (1, -1),\ (-1, 1),\ (-1, -1) \]

If you can find the word in the grid following these rules, print YES; otherwise, print NO.

inputFormat

The first line contains two integers \( R \) and \( C \) separated by a space, representing the number of rows and columns in the grid.

The next \( R \) lines each contain a string of exactly \( C \) characters representing the grid.

The last line contains the word to search for.

outputFormat

Output a single line: YES if the word exists in the grid according to the given rules, or NO if it does not.

4 4
abcf
bdef
dhag
ehkf
beak

YES