#P4111. [Wf2015]Keyboarding

    ID: 3319 传统题 1000ms 512MiB 尝试: 233 已通过: 59 难度: 5 上传者: 标签>难度分类普及+/提高-枚举与搜索广度优先搜索图论状态扩展图状态编码状态去重模拟与实现技巧预计算转移CF1700鸣谢phile提供译文

[Wf2015]Keyboarding

[ICPC2015 WF] Keyboarding

题目描述

一块虚拟键盘由 rr 行 cc 列的方格组成。同一个键可以占据相邻的多个方格,这些方格连成一个整体。设备有五个实体按钮:上、下、左、右和选择。光标起初位于左上角方格。

按方向按钮后,光标沿该方向越过属于当前键的方格,停在遇到的第一个属于其他键的方格;若沿该方向找不到这样的方格,光标不动。按选择按钮时,键入光标所在键的字符,光标留在所在方格。输入完文本后,还要移动到回车键并按选择。

样例 1 的虚拟键盘、实体按钮和光标路线

红点表示按下选择按钮。样例 1 中,按图中的路线输入 CONTEST 和回车共需 3030 次按键。

输入格式

第一行两个整数 r,cr,c(1≤r,c≤501\le r,c\le50)。接下来 rr 行,每行 cc 个字符,描述键盘布局。字符只能是大写英文字母、数字、连字符 - 或星号 *(表示回车)。同一个字符对应一个键,其所有格子组成一个连通区域。

最后一行是长度为 11 到 10 00010\,000 的待输入文本,不含星号,只使用键盘上存在的字符。保证可以输入这段文字并结束。

输出格式

输出最少的实体按钮按下次数。方向按钮和选择按钮各按一次都算一次。必须计入最后输入回车的操作。

样例 #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