Word Search in a Matrix

You are given an \( m \times n \) grid of characters and a target word. Your task is to 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. Each cell may be used only once in the construction of the word.

Note: Use a depth-first search (DFS) or backtracking approach to navigate through the grid.

Example:

Input:
[ ["A", "B", "C", "E"],
  ["S", "F", "C", "S"],
  ["A", "D", "E", "E"] ], "ABCCED"
Output:
true

</p>

In the above example, the word can be found following the path A \(\rightarrow\) B \(\rightarrow\) C \(\rightarrow\) C \(\rightarrow\) E \(\rightarrow\) D. (Recall \( k = |word| \) indicates a successful match.)

inputFormat

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

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

outputFormat

Output to stdout a single line containing either true or false (without quotes), indicating whether the target word exists in the matrix.

## sample

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

true