P15727 [JAG 2023 Summer Camp #3] Edit distance on table

你有一个 $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$ 之间可能的最小编辑距离。

翻译由 DeepSeek V3.2 完成