说明

你有一个 $H$ 行 $W$ 列的表格。表格的每个单元格包含一个字母。

你将通过以下步骤构造一个字符串：

• 步骤 1：在表格中选择一个单元格，令 $S$ 为一个长度为 $1$ 的字符串，其中包含该单元格中的字母。
• 步骤 2：执行以下两种操作之一：
  • 停止构造 $S$，或者
  • 从与当前单元格共享一条边的四个单元格中选择一个单元格。然后，将该单元格中的字母追加到 $S$ 的末尾，并移动到该单元格。接着，重复步骤 2。

你还有一个字符串 $T$。你的任务是最小化 $S$ 与 $T$ 之间的编辑距离。

字符串 $U$ 和 $V$ 之间的编辑距离（也称为莱文斯坦距离）是指通过以下操作将 $U$ 转换为 $V$ 所需的最少步数：

• 将 $U$ 中的一个字符替换为另一个字符。
• 在 $U$ 中插入一个字符。
• 从 $U$ 中删除一个字符。

输入格式

输入包含一个单独的测试用例，格式如下：

$$\begin{aligned} &H \ W \\ &c_{1,1} c_{1,2} \ldots c_{1,W} \\ &c_{2,1} c_{2,2} \ldots c_{2,W} \\ &\vdots \\ &c_{H,1} c_{H,2} \ldots c_{H,W} \\ &T \end{aligned}$$

$H$ 和 $W$（$2 \leq H, W \leq 100$）分别表示表格的高度和宽度。$c_{i,j}$（$1 \leq i \leq H$，$1 \leq j \leq W$）是第 $i$ 行第 $j$ 列单元格中的字符。$T$ 是一个非空字符串。$T$ 的长度不超过 $2,000$。$c_{i,j}$ 和 $T$ 均由小写英文字母组成。

输出格式

在一行中输出 $S$ 与 $T$ 之间可能的最小编辑距离。

2 2
ab
ar
abracadabra

2

提示

翻译由 DeepSeek V3.2 完成