Word Search in Matrix

Given a matrix of characters and a word, determine whether the word can be constructed by sequentially adjacent letters in the matrix. Adjacent cells are those that are horizontally, vertically, or diagonally neighboring. Each cell can be used at most once in the construction of the word.

Formally, you are given an (N \times M) grid of uppercase characters and a string (word). You must decide if there exists a path in the grid such that the concatenation of the characters along the path equals (word). The path can start from any cell and moves can be made in any of the eight possible directions:

$$\{ (1,0), (-1,0), (0,1), (0,-1), (1,1), (-1,-1), (1,-1), (-1,1) \} $$

For example, consider the board:

ABCE
SFCS
ADEE
AFAE

For the word "ABCCED", there exists a valid path. Your task is to implement a solution that reads the board and the word from standard input and prints "true" if such a path exists, or "false" otherwise.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers (N) and (M), representing the number of rows and columns of the matrix.
• The next (N) lines each contain a string of exactly (M) uppercase letters, representing the rows of the matrix.
• The last line contains the string (word) to be searched in the matrix.

outputFormat

Print a single line to standard output (stdout) containing either "true" or "false" (without quotes) to indicate whether the word exists in the matrix.## sample

4 4
ABCE
SFCS
ADEE
AFAE
ABCCED

true