Word Search in Grid

Given an m \(\times\) n 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. Note that the same letter cell may not be used more than once.

The problem can be mathematically formulated as follows: Given a grid \(G\) with indices \(0 \leq i < m\) and \(0 \leq j < n\) and a word \(w\) of length \(k\), determine if there exists a sequence of indices \((i_0, j_0), (i_1, j_1), \dots, (i_{k-1}, j_{k-1})\) such that \(G[i_l][j_l] = w[l]\) for \(0 \leq l < k\) and each pair \((i_{l+1}, j_{l+1})\) is adjacent (horizontally or vertically) to \((i_l, j_l)\), with no cell reused.

inputFormat

The first line contains two integers m and n, representing the number of rows and columns respectively. Each of the following m lines contains a string of n characters representing a row of the grid. The last line contains the target word. The input is provided via standard input (stdin).

outputFormat

Output "YES" if the word exists in the grid following the given rules; otherwise, output "NO". The output should be written to standard output (stdout).## sample

3 4
ABCE
SFCS
ADEE
ABCCED

YES