Find Pattern in a 2D Grid

You are given a 2D grid of characters of dimensions \(R \times C\) and a target string \(P\). Your task is to determine whether the pattern \(P\) exists in the grid by starting from any cell that matches \(P[0]\) and then moving in any of the 8 possible directions (up, down, left, right, and the 4 diagonals) without revisiting a cell in the current path. In other words, you need to check if there exists a contiguous path in the grid such that the sequence of characters along the path equals the given pattern.

Movement Rules:

• You may move to any of the adjacent cells (horizontally, vertically, or diagonally).
• You cannot use the same cell more than once in a single matching path.

The problem can be formalized as follows: given a grid \(G\) of dimensions \(R \times C\) and a string \(P\) of length \(L\), determine if there exists a sequence of coordinates \((i_1, j_1), (i_2, j_2), \ldots, (i_L, j_L)\) such that:

[ \begin{aligned} G[i_1][j_1] &= P[0], \ G[i_2][j_2] &= P[1], \ &;\vdots \ G[i_L][j_L] &= P[L-1], \ \end{aligned} ]

and for every \(k\) where \(1 \leq k < L\), the cell \((i_k, j_k)\) is adjacent (in one of 8 directions) to \((i_{k+1}, j_{k+1})\), with no cell being reused in the sequence.

inputFormat

The input is provided via standard input (stdin) in the following format:

R C
row1
row2
... 
rowR
P

Where:

• \(R\) and \(C\) are integers representing the number of rows and columns of the grid.
• Each of the next \(R\) lines contains a string of exactly \(C\) characters representing a row of the grid.
• \(P\) is the pattern string to search for in the grid.
</p>

outputFormat

Output a single line to standard output (stdout) that is either True if the pattern exists in the grid according to the movement rules, or False otherwise.

## sample

3 4
abce
sfcs
adee
abcced

True