打字 keyboarding

题目背景

输入一条信息需要敲几下键？或许你会认为它等于文本中的字符数，但只有在按键与字符一一对应时方才如此。对于掌上设备来说，输入文本通常很麻烦。有些设备只提供几个按钮，比字母数量少得多。对于这样的设备，键入一个字符就需要一系列操作。

现在就有一套这样的输入机制：屏幕虚拟键盘，上面有一个光标，可以在键与键移动来选择字符。四个箭头按钮控制光标的移动，当光标的位置在合适的键上时，按确认按钮即可选中相应的字符并将其输入，且文本的末尾必须回车。

题目描述

现在给你一段字符串，并且你只有这五个按钮。本题中，你会得到一个虚拟键盘布局。你的任务是确定键入给定文本所需的最少操作数，按下一个按钮即视为一次操作。键分布在一个矩形网格中，这样每个虚拟键占用网格中一个或多个相连的单元方格。光标从左上角开始并可四向移动，且每次都必须移到不同键上。同一种按键间光标不能移动。

输入格式

输入文件包含几个测试用例，每个用例如下。

输入的第一行包含两个整数 $r$ 和 $c$ $(1≤r, c≤50)$，分别为虚拟键盘网格的行数和列数。在接下来的 $r$ 行中，每行有 $c$ 个字符，为大写字母、数字、横杠或星号（表示Enter）之一，每块虚拟键与字符唯一对应。

每个键由一个或多个方格组成，这些方格形成相连区域。最后一行为要输入的文本，是一个非空字符串，最多有10000个除星号外的有效字符。

输出格式

对于每个测试用例，输出键入整个文本所需的最少操作数，包括最后按下的回车键，其保证这段信息被成功输入。

样例

样例输入

4 7
ABCDEFG
HIJKLMN
OPQRSTU
VWXYZ**
CONTEST
5 20
12233445566778899000
QQWWEERRTTYYUUIIOOPP
-AASSDDFFGGHHJJKKLL*
--ZZXXCCVVBBNNMM--**
--------------------
ACM-ICPC-WORLD-FINALS-2015
2 19
ABCDEFGHIJKLMNOPQZY
X*****************Y
AZAZ
6 4
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB

样例输出

30
160
19
7

提示

样例说明参照原题文件中的图片。

数据规模

• $1\le r,c\le 50, |S|\le10000$ 。

翻译: @QQzhi