UVA1714 Keyboarding

## 题目背景 输入一条信息需要敲几下键？或许你会认为它相当于文本中的字符数，但只有在按键与字符一一对应时方才如此。对于小型设备来说，输入文本通常很麻烦。有些设备只提供几个按钮，比字符数量少得多。对于这样的设备，键入一个字符就需要一系列操作。 现在就有一套这样的输入机制：屏幕虚拟键盘，上面有一个光标，可以在键与键来回移动来选择字符。四个箭头按钮控制光标的移动，当光标的位置在合适的虚拟键上时，按确认按钮即可输入相应的字符，且在文本的末尾必须回车。 现在给你一段字符串，并且你只有「上、下、左、右，确认」这五个按钮。本题中，你会得到一个虚拟键盘布局。你的任务是确定键入给定文本所需的最少操作数，按下一个按钮即视为一次操作。虚拟键分布在一个矩形网格中，这样每个虚拟键占用网格中一个或多个相连的单元方格。光标初始均在左上角并可四向移动，且每次都沿该方向移到下一个不同字符的虚拟键。光标不能移动到无效的格上。 每个虚拟键与字符唯一对应，其由一个或多个方格组成，这些方格相连为一块区域。

无

无

 插图描述了一种经过30次操作后输入 `CONTEST` 的方式，红点表示按下该虚拟键。 #### 数据规模 - $1\le r,c\le50,|S|\le 100001\le r,c\le 50,|S|\le 10000$。 --- 翻译: @QQzhi (UID:525682)