2D Grid Pattern Search

Given a two-dimensional grid where each cell contains a single character, determine whether a specified pattern can be traced in the grid. The pattern can be constructed from consecutive cells by moving from one cell to an adjacent cell. The allowed moves are up, down, left, right, and the four diagonal directions. No cell may be used more than once in forming the pattern. If the pattern is empty, the answer is True. If the grid is empty, the answer is False.

The movement directions can be expressed in LaTeX as follows. If the current cell is at position \((i,j)\), then the eight possible moves are given by:

[ (i + \Delta i,, j + \Delta j)\quad \text{where}\quad \Delta i,\Delta j \in {-1,0,1} \quad \text{and} \quad (\Delta i,\Delta j) \neq (0,0). ]

Your task is to decide if the pattern exists in the grid following the movement rules above.

inputFormat

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

n m
row_1
row_2
... (n rows total)
pattern

Here, n and m are two integers representing the number of rows and columns of the grid, respectively. Each of the next n lines contains a string of length m representing a row of the grid. The last line is a string that denotes the pattern to search for. Note that the pattern can be an empty string.

outputFormat

The output is written to stdout and should be a single line containing either True if the pattern is found in the grid, or False otherwise.

4 4
abcd
efgh
ijkl
mnop
bfk

True