Minimum Keystrokes on a Virtual Keyboard

You are given a description of a virtual keyboard layout and a text message that needs to be typed using a cursor controlled by five hardware buttons. The virtual keyboard is represented as a rectangular grid where each key occupies one or more contiguous unit squares. The cursor initially starts at the upper left corner of the grid. There are five buttons: four arrow buttons (up, down, left, right) and a select button.

When an arrow button is pressed, the cursor moves in that direction. However, instead of moving to the immediately adjacent square, the cursor skips over unit squares that belong to the same key as the current square and lands on the next unit square that belongs to a different key. If no such square exists in that direction, the cursor does not move. When the select button is pressed, the character on the key under the cursor is appended to the output text.

To finish entering the message, the user must finally press the select button when the cursor is over the Enter key. In our grid, the Enter key is represented by the character #.

Given the grid layout and a text message T, your task is to compute the minimum number of strokes (arrow moves or select presses) required to type out the message followed by Enter. Formally, let T' = T concatenated with '#' (the Enter key). Starting from the upper left corner of the grid, find the least number of strokes needed so that, by applying a sequence of moves (each move costing 1 stroke), you can obtain T' as the typed output.

The behavior when an arrow button is pressed is defined as follows. Suppose the cursor is currently at cell (r, c) and the key at that cell is denoted by K. When moving in a given cardinal direction (for example, to the right), the cursor looks at the subsequent cells in that direction. It skips over cells that belong to the same key K and stops at the first cell that contains a key different from K. If no cell in that direction qualifies (i.e. if the cursor would move off the grid without encountering a different key), then the cursor remains in its current position.

Note that pressing any button (arrow or select) counts as one stroke.

Input constraints and assumptions:

• The grid dimensions and the text are given in the input.
• The grid has R rows and C columns.
• Each of the next R lines contains C characters representing the keyboard layout. Each key is represented by a character. The Enter key is represented by #.
• The last line of input is a string consisting of the characters to be typed (excluding Enter). You must append the Enter key (i.e. #) to this text in your simulation.

Example:

3 3
ABC
DEF
G#H
BAD

One possible sequence of moves to type the message "BAD" and then Enter is as follows:

• Start at (0,0) which is 'A'. Move right to (0,1) to get 'B' then select (2 strokes).
• From (0,1), move left to (0,0) to get 'A' then select (2 strokes).
• From (0,0), move down to (1,0) to get 'D' then select (2 strokes).
• Finally, move from (1,0) to reach the Enter key '#' and select it (3 strokes, for example: right then down then select).

The answer for this example is 9 strokes.

inputFormat

The input begins with a line containing two integers R and C (the number of rows and columns of the keyboard grid). Following this, there are R lines each containing C characters (with no spaces) representing the keyboard layout. The Enter key is represented by the character #. The last line of input contains a non-empty string S consisting of the characters to be typed (excluding Enter). You should append the Enter key (i.e. #) to the end of S when processing.

R C
row1
row2
...
rowR
S

outputFormat

Output a single integer — the minimum number of strokes required to type the message S followed by the Enter key.

sample

3 3
ABC
DEF
G#H
BAD

9