Word Search in a Grid

Given a two-dimensional grid of characters and a target word, determine if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are those horizontally or vertically neighboring. The same cell may not be used more than once in a single word search.

Note: Use backtracking or depth-first search to try different paths in the grid until the word is found or all possibilities are exhausted.

Mathematically, if we denote the grid as \(G\) and the word as \(w = w_1w_2...w_k\), then there exists a sequence of positions \((i_1,j_1), (i_2,j_2), ..., (i_k,j_k)\) such that for every \(1 \leq t \leq k\), \(G[i_t][j_t] = w_t\) and for \(1 \leq t < k\), the positions \((i_t,j_t)\) and \((i_{t+1},j_{t+1})\) are adjacent (i.e. share a common side).

inputFormat

The first line of input contains two integers \(m\) and \(n\) indicating the number of rows and columns in the grid respectively.

The next \(m\) lines each contain a string of length \(n\) representing a row of the grid.

The last line contains the target word.

Input is read from standard input (stdin).

outputFormat

Output a single line with either True or False indicating whether the target word exists in the grid.

Output is written to standard output (stdout).

## sample

3 4
ABCE
SFCS
ADEE
ABCCED

True