You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

出自 ICPC World Final 2015 F. Keyboarding

给定一个 $r$ 行 $c$ 列的在电视上的「虚拟键盘」，通过「上，下，左，右，选择」共 $5$ 个控制键，你可以移动电视屏幕上的光标来打印文本。一开始，光标在键盘的左上角，每次按方向键，光标总是跳到下一个在该方向上与当前位置不同的字符，若不存在则不移动。每次按选择键，则将光标所在位置的字符打印出来。
现在求打印给定文本（要在结尾打印换行符）的最少按键次数。

输入格式

第一行输入 $r,c$。
接下来给出一个 $r\times c$ 的键盘，包括大写字母，数字，横线以及星号（星号代表 Enter 换行）。
最后一行是要打印的文本串 $S$，$S$ 的长度不超过 $10000$。

输出格式

输出打印文本（包括结尾换行符）的最少按键次数。保证一定有解。

样例 1

2 19
ABCDEFGHIJKLMNOPQZY
X*****************Y
AZAZ

19

1. 键入 A $1$ 次
2. 下（X）右（*）右（Y）左（*）上（Z），移动 $5$ 次
3. 键入 Z $1$ 次
4. 下（*）左（X）上（A），移动 $3$ 次
5. 键入 A $1$ 次
6. 从 A 移动到 Z $5$ 次
7. 键入 Z $1$ 次
8. 下（*），移动 $1$ 次
9. 键入 * $1$ 次

5 20
12233445566778899000
QQWWEERRTTYYUUIIOOPP
-AASSDDFFGGHHJJKKLL*
--ZZXXCCVVBBNNMM--**
--------------------
ACM-ICPC-WORLD-FINALS-2015

160

6 4
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB

7

数据范围与提示

对于 $100\%$ 的数据，$1\le r,c\le 50$，$S$ 的长度不超过 $10000$。