AT_past17_g.蛇行する文字列

给定一个包含 $H$ 行 $W$ 列的网格。我们用 $(i, j)$ 表示从上到下第 $i$ 行、从左到右第 $j$ 列的格子。
每个格子上写着一个小写英文字母。$(i, j)$ 格子上的字母记为 $G_{i, j}$。
现在给定一个长度为 $N$ 的字符串 $S$。请判断是否存在一组格子序列 $(a_1, b_1)$, $(a_2, b_2)$, $\dots$, $(a_N, b_N)$，满足下列所有条件？若存在，输出 Yes，否则输出 No。

• $(a_1, b_1)$, $(a_2, b_2)$, $\dots$, $(a_N, b_N)$ 互不相同。
• 对任意 $i$，$(a_i, b_i)$ 和 $(a_{i+1}, b_{i+1})$ 在八个方向上相邻。换言之，$\max(\vert a_i - a_{i+1} \vert, \vert b_i - b_{i+1} \vert) = 1$。
• $(a_i, b_i)$ 上的字母等于 $S$ 的第 $i$ 个字符。

输入按以下格式从标准输入读入：

$H$ $W$
$G_{1,1}G_{1,2}\dots G_{1,W}$
$G_{2,1}G_{2,2}\dots G_{2,W}$
$\vdots$
$G_{H,1}G_{H,2}\dots G_{H,W}$
$N$
$S$

如果存在一组符合要求的格子序列，输出 Yes；否则输出 No。

样例解释 1

格子序列 $(2, 1), (3, 2), (2, 3), (1, 2), (1, 1)$ 满足所有题目要求，所以答案为 Yes。

数据范围

• $1 \leq H, W \leq 10$
• $G_{i, j}$ 是小写英文字母。
• $1 \leq N \leq 5$
• $S$ 是一个长度为 $N$ 的仅由小写英文字母组成的字符串。

由 ChatGPT 5 翻译