Word Search in Grid

You are given a grid of characters and a word. Your task is to determine whether the word can be constructed from letters of sequentially adjacent cells in the grid. The adjacency is defined to include horizontal, vertical, and diagonal neighboring cells. Note that each cell can be used at most once in constructing the word.

The word is searched by starting from any cell in the grid and moving to one of its 8 neighbors. If it is possible to form the word by following these rules, output True; otherwise, output False.

Hint: Use a depth-first search (DFS) based backtracking approach to explore potential paths.

inputFormat

The input is given through standard input (stdin) with the following format:

1. The first line contains two space-separated integers m and n representing the number of rows and columns in the grid.
2. The next m lines each contain a string of n uppercase English letters representing a row of the grid.
3. The last line contains the word to search for in the grid.

outputFormat

Output a single line to standard output (stdout) containing either True if the word exists in the grid (according to the rules), or False otherwise.

3 4
ABCE
SFCS
ADEE
ABCCED

True