P6909 [ICPC 2015 WF] Keyboarding

输入一个文本消息需要多少次按键？你可能认为这等同于文本中的字符数，但这仅在一次按键生成一个字符时才正确。对于口袋大小的设备，输入文本的可能性通常受到限制。有些设备仅提供少量按钮，远少于字母表中的字母数量。对于这样的设备，输入一个字符可能需要多次按键。为了解决这些限制，一种机制是在屏幕上显示虚拟键盘，并提供一个可以从一个键移动到另一个键的光标来选择字符。四个方向键控制光标的移动，当光标位于适当的键上时，按下第五个按钮选择相应的字符并将其附加到文本末尾。要终止文本，用户必须导航到并选择 Enter 键。这使用户可以使用任意字符集并仅用五个硬件按钮输入任意长度的文本。 在这个问题中，给定一个虚拟键盘布局，你的任务是确定输入给定文本所需的最少按键次数，其中按下任何一个五个硬件按钮都算作一次按键。键以矩形网格排列，每个虚拟键占据网格的一个或多个连接单元格。光标从键盘的左上角开始，并在四个基本方向上移动，以便它总是跳到该方向上属于不同键的下一个单元格。如果没有这样的单元格，光标不会移动。  图 1：样例输入 1。一个示例虚拟键盘和硬件按钮。 图 1，说明了样例输入 1，展示了一种在示例虚拟键盘上使用 30 次按键输入 CONTEST 的可能方式。红点表示按下选择按钮的虚拟键。

输入的第一行包含两个整数 $r$ 和 $c$ ($1 \leq r, c \leq 50$)，表示虚拟键盘网格的行数和列数。虚拟键盘在接下来的 $r$ 行中指定，每行包含 $c$ 个字符。这些字符的可能值是大写字母、数字、一个破折号和一个星号（表示 Enter）。每个字符仅对应一个键。每个键由一个或多个网格单元组成，这些单元将始终形成一个连接区域。输入的最后一行包含要输入的文本。此文本是一个最多包含 $10\, 000$ 个可用字符（不包括星号）的非空字符串。

显示输入整个文本所需的最少按键次数，包括最后的 Enter 键。保证文本可以被输入。

时间限制：3000 毫秒，内存限制：1048576 KB。 国际大学生程序设计竞赛（ACM-ICPC）世界总决赛 2015。 题面翻译由 ChatGPT-4o 提供。