Word Search in Matrix

You are given an (N \times M) matrix of uppercase letters and a target word. The task is to determine whether the word exists in the matrix by moving from one letter to any adjacent letter in any of the 8 possible directions (horizontal, vertical, or diagonal). During the search, each cell may be used at most once. This problem requires you to implement a depth-first search (DFS) algorithm with backtracking to explore all possible paths starting from any cell matching the first letter of the word.

inputFormat

The input is given via standard input (stdin). The first line contains two integers (N) and (M) representing the number of rows and columns of the matrix, respectively. Each of the next (N) lines contains (M) space-separated uppercase letters representing the matrix rows. The final line contains a string consisting of uppercase letters, which is the word to search for.

outputFormat

Output via standard output (stdout) a single line: either 'True' if the word exists in the matrix according to the rules, or 'False' otherwise.## sample

4 5
A B C E F
S F C S A
A D E E B
C E E E G
ABCCED

True