题目描述

出自 ICPC World Final 2015 F. Keyboarding

给定一个 $r$ 行 $c$ 列的电视「虚拟键盘」。你可以通过「上、下、左、右、选择」共 $5$ 个控制键移动电视屏幕上的光标并打印文本。

一开始，光标位于键盘左上角。每次按方向键时，光标会跳到该方向上第一个与当前位置字符不同的位置；若不存在这样的位置，则光标不移动。每次按选择键，则会打印光标所在位置的字符。

现在要求打印给定文本，并在结尾打印换行符，求所需的最少按键次数。

输入格式

第一行包含两个整数 $r,c$。

接下来 $r$ 行，每行包含 $c$ 个字符，表示虚拟键盘。键盘字符包括大写字母、数字、横线以及星号，其中星号 * 代表 Enter 换行。

最后一行包含一个字符串 $S$，表示需要打印的文本。

输出格式

输出一个整数，表示打印文本并在结尾打印换行符所需的最少按键次数。

保证一定有解。

样例

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

19

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

160

6 4
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB

7

数据范围与提示

• $1 \le r,c \le 50$
• $S$ 的长度不超过 $10000$

来源

一本通 1.4 练习 2