Problems
The left side of Figure 1 shows a 4×7 virtual keyboard. To type text, the user must use the five hardware buttons shown on the right, instead of pressing the virtual keys directly. A “cursor” starts at the top-left key of the virtual keyboard, and the four arrow buttons control its movement. Pressing an arrow once moves the cursor in that direction until it reaches a different character; if there is no such character, the cursor does not move. When the cursor is on a desired key, pressing the select (SEL) button chooses that character and appends it to the end of the text. In this way the given text can be entered. To finish the input, the user must find and select the Enter key (i.e., press the select button on it).
Figure 1. Example of a virtual keyboard and hardware buttons
Figure 1 illustrates how to type the text CONTEST on the given virtual keyboard. The arrows show the cursor’s movement as the arrow buttons are pressed, and the dots indicate the virtual keys on which the select button is pressed. You can also see that typing CONTEST requires 30 key presses.
In this problem, the virtual keyboard layout is given along with the text to type. You must find the minimum number of key presses needed to enter the text.
Input
The first line contains two integers r and c (1 ≤ r, c ≤ 50), the number of rows and columns in the virtual keyboard grid. The next r lines describe the keyboard, each containing c characters. Possible characters are uppercase letters, digits, hyphens, and asterisks (which represent Enter). Each character corresponds to exactly one key. Each key consists of one or more grid squares and always forms a connected region. The last line contains the text to be entered. This text is a non-empty string of at most 10,000 characters, contains no asterisks, and can be typed using the given keyboard.
Output
Display the minimum number of key presses required to type the entire text, including the final Enter key.
Example #1
4 7
ABCDEFG
HIJKLMN
OPQRSTU
VWXYZ**
CONTEST
30
Example #2
5 20
12233445566778899000
QQWWEERRTTYYUUIIOOPP
-AASSDDFFGGHHJJKKLL*
--ZZXXCCVVBBNNMM--**
--------------------
ACM-ICPC-WORLD-FINALS-2015
160
Example #3
2 19
ABCDEFGHIJKLMNOPQZY
X*****************Y
AZAZ
19
Example #4
6 4
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB
7
You must sign in to write code.