Word Search in a Grid

You are given a grid of characters and a target word. Your task is to determine whether the word exists in the grid. The word must be constructed from letters of sequentially adjacent cells, where two cells are considered adjacent if they share an edge (i.e., up, down, left, or right). In other words, if a cell is at position \( (i,j) \), then any cell at \( (i \pm 1, j) \) or \( (i, j \pm 1) \) is adjacent (note that the condition can be expressed as \(|i_1 - i_2| + |j_1 - j_2| = 1\)). Also, the same cell may not be used more than once in constructing the word.

For example, consider the following grid:

A B C E
S F C S
A D E E

If the target word is "ABCCED", then the word exists in the grid. However, if the word is "ABCB", it cannot be formed under the given rules.

inputFormat

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

• The first line contains two integers \( m \) and \( n \), representing the number of rows and columns of the grid, respectively.
• The next \( m \) lines each contain \( n \) characters (separated by spaces) representing the grid.
• The last line contains the target word.

outputFormat

Output a single line to stdout which is either True if the word exists in the grid according to the above rules, or False otherwise.

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

True