Kinky Word Searches

Interview

Time limit6sMemory limit1024 MB

Summary

Given a letter grid, decide whether a target word can be traced with exactly k direction changes, where the path may reuse cells but cannot stay put.

Level: Medium7 of 10
Topics: DFS, Backtracking, Implementation, Brute force
Solved: No attempts yet

Problem

You are probably familiar with regular word searches, where you are given a grid of letters and a word to find. The word can lie in a straight line horizontally, vertically, or diagonally (and perhaps backwards in any of those directions). For example, here is a grid of letters:

Figure 1: A word search grid

The word "JAVA" can be found going from the bottom right corner diagonally upwards.

In a kinky word search the path that spells out the word can have one or more "kinks": places where the path changes direction. For example, in the given grid you can spell the word "PYTHON" with $3$ kinks (one each at the T, H, and O):

Figure 2: A kinky spelling of "PYTHON"

Allowing kinks lets letters be reused: the word "CPLUSPLUS" can be found in the upper right corner of the grid (with $5$ kinks). However, you cannot stay on a letter twice in a row, so you cannot spell the word "HASKELL" in this grid (though you can find at least $11$ more common programming languages). Your task is to determine whether spelling a word with a given number of kinks is possible.

Input

The input begins with a line containing two positive integers $r$ and $c$ ( $r, c \leq 10$ ), the number of rows and columns in the grid. After this are $r$ rows of $c$ uppercase characters. Letters are separated by a space. After the grid are two lines: the first line is an integer $k$ , the number of kinks. The second line contains an uppercase word to look for, with maximum length $100$ .

Output

Output YES if it is possible to spell the given word with exactly $k$ kinks on the grid provided, or NO if it is not.

Examples3

Example 1

Input

5 5
L M E L C
C A K U P
D O V S Y
R N L A T
P G O H J
0
JAVA

Expected output

YES

Example 2

Input

5 5
L M E L C
C A K U P
D O V S Y
R N L A T
P G O H J
3
PYTHON

Expected output

YES

Example 3

Input

5 5
L M E L C
C A K U P
D O V S Y
R N L A T
P G O H J
4
PYTHON

Expected output

NO