AT_wupc_06 僕は宇宙人

我是宇宙人。经过漫长的旅途，我从遥远的地方来到了这里。地球真是个好地方呢。 宇宙人使用的通信板是一个由 $N$ 行 $M$ 列格子组成的板子。每个格子上只写有一个字母。宇宙人通过如下规则在这个板子上移动来传递信息。 1. 站在板子的任意一个格子上。 2. 从当前位置选择一个前进方向（左、右、上、下）中的一个。除了第一次外，这次选择的方向不能和上一次前进的方向相同。 3. 沿着选定的方向前进，直到找到下一个要传递的字母为止。 - 如果在移动过程中出了板子，则传递失败。 - 移动时，根据前进的格子数会产生相应的代价。前进 $x$ 个格子的代价为 $x$。 4. 在前进过程中一旦找到要传递的字母，立即停止。 5. 如果要传递的字母已经全部传递完毕，则传递结束。如果还有未传递的字母，则返回第 2 步。 这种信息传递方式的问题在于，不同的方向选择可能导致传递失败，或者移动代价过高。 因此，你的任务是：给定板上的字母和要传递的字符串，判断是否能够完成传递；如果可以，求出最小的传递代价。 输入按以下格式从标准输入读入。 > $N\ M\ L$ $S$ $c_{1,1}c_{1,2}\ ...\ c_{1,M}$ $c_{2,1}c_{2,2}\ ...\ c_{2,M}$ $\ldots$ $c_{N,1}c_{N,2}\ ...\ c_{N,M}$ - 第 1 行给出板子的大小 $N$（$1 \leq N \leq 100$）、$M$（$1 \leq M \leq 100$），以及要传递的字符串长度 $L$（$1 \leq L \leq 100$），用半角空格分隔。 - 第 2 行给出只包含小写字母、长度为 $L$ 的字符串 $S$，表示宇宙人要传递的信息。 - 第 3 行到第 $N+2$ 行，每行给出 $M$ 个小写字母，表示板子上的字母。 请输出完成信息传递所需的最小代价。如果无法完成传递，则输出 "-1"。 最后请输出换行符。 例如： ``` 3 3 2 ab xzz azb zzz ``` 输出： ``` 3 ``` 例如： ``` 3 4 2 ab xzza azzz zzbz ``` 输出： ``` -1 ```

第 1 行：三个整数 $N\ M\ L$，用空格分隔。 第 2 行：长度为 $L$ 的小写字母字符串 $S$。 第 3 行到第 $N+2$ 行：每行 $M$ 个小写字母，表示板子上的字母。

如果可以完成传递，输出最小代价。否则输出 $-1$。最后输出换行符。

无。 由 ChatGPT 4.1 翻译