#P4111. [Wf2015]Keyboarding
[Wf2015]Keyboarding
[ICPC2015 WF] Keyboarding
题目描述
一块虚拟键盘由 行 列的方格组成。同一个键可以占据相邻的多个方格,这些方格连成一个整体。设备有五个实体按钮:上、下、左、右和选择。光标起初位于左上角方格。
按方向按钮后,光标沿该方向越过属于当前键的方格,停在遇到的第一个属于其他键的方格;若沿该方向找不到这样的方格,光标不动。按选择按钮时,键入光标所在键的字符,光标留在所在方格。输入完文本后,还要移动到回车键并按选择。

红点表示按下选择按钮。样例 1 中,按图中的路线输入 CONTEST 和回车共需 次按键。
输入格式
第一行两个整数 ()。接下来 行,每行 个字符,描述键盘布局。字符只能是大写英文字母、数字、连字符 - 或星号 *(表示回车)。同一个字符对应一个键,其所有格子组成一个连通区域。
最后一行是长度为 到 的待输入文本,不含星号,只使用键盘上存在的字符。保证可以输入这段文字并结束。
输出格式
输出最少的实体按钮按下次数。方向按钮和选择按钮各按一次都算一次。必须计入最后输入回车的操作。
样例 #1
样例输入 #1
4 7
ABCDEFG
HIJKLMN
OPQRSTU
VWXYZ**
CONTEST
样例输出 #1
30
样例 #2
样例输入 #2
5 20
12233445566778899000
QQWWEERRTTYYUUIIOOPP
-AASSDDFFGGHHJJKKLL*
--ZZXXCCVVBBNNMM--**
--------------------
ACM-ICPC-WORLD-FINALS-2015
样例输出 #2
160
样例 #3
样例输入 #3
2 19
ABCDEFGHIJKLMNOPQZY
X*****************Y
AZAZ
样例输出 #3
19
样例 #4
样例输入 #4
6 4
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB
样例输出 #4
7