Transcript
A company wants to hire a new employee. The selection process
consists of several attention tests, one of them consists in: each candidate
must type each character he sees in a flashing screen, using a given keyboard.
You are asked to write down a program to score the candidates, given the
original sequence of characters, and what the candidate actually typed. Scoring
is based on the kind of actions the candidate may perform. For each character
flashing in the screen, she may only:
1.
Correctly type the character;
2.
Omit the character;
3.
By mistake, type a different
character.
The score or
penalty given to each action depends on the keyboard layout considered. The keyboard
is a matrix of n rows and m columns.
The distance between the characters at coordinates (i1,j1)
and (i2,j2) is given by the maximum of |i1- i2|
and |j1-j2|. For example, in the keyboard below (3 rows
by 5 columns), the distance between the character "a", at (2,1), and the
character "h" at (3,5) is 4, and the distance between the character "o" and "h" is 2. In this
example, the largest distance between any two characters is 4. For any keyboard
the largest distance between any two characters is conventionally referred to
by TOP.
|
1 |
e |
g |
y |
i |
m |
|
2 |
a |
n |
o |
w |
s |
|
3 |
u |
f |
l |
t |
h |
|
|
1 |
2 |
3 |
4 |
5 |
The
score given to the correct transcription of one character is TOP+1. The penalty
given for the omission of one character (action 2) is TOP+1. The score given
for changing a character for another (action 3) is TOP+1 minus the distance
between the two characters involved in the mistake. For example, considering the keyboard shown above, the
following action scores apply: Score for the correct transcript of one
character: 5; Penalty for the omission of one character: 5; Score for changing
character "o" to character "h": 5-2=3.
A
scoring of a test is the sum of the scores given to each character typed minus
the sum of the penalties for each character omitted. Since the scoring is only
done after the test finishes, it is not possible to be sure about when specific
actions were realized (e.g, did the candidate skip a character, or mistyped
it?). To avoid complaints, the final score given is the highest possible
value for scoring
the candidate, according to the rules explained above. For example, if the text
to transcribe is "time" and the candidate types "yme", we may score it in
several ways:
To omit "t", change "i" for
"y" and correctly transcribe "m" and "e";
To change "t" for "y", omit "i" and correctly transcribe "m" and "e";
To change "t" for "y", change "i" for "m", omit "m" and correctly
transcribe "e";
To change "t" for "y", change "i" for "m", change "m" for "e" and omit
"e".
Each one of these possibilities has one score associated
(9, 8, 7, and 3 points, respectively). Thus, the candidateÕs final score is 9
points. Write a program that, considering the shape of a keyboard, the text to
be transcribed by the candidate, and the actual transcript produced by the
candidate returns the final score of the candidate.
Input
The first line
contains an integer N, stating the number of rows in the keyboard. The next N
lines, all with the same length, contain a string with the sequence of
characters in the corresponding keyboard row. The keyboard will not have more than 20 rows and 30 columns.
Then, the next two lines contains the text to be transcribed by the candidate,
and the text typed by the candidate. These texts will be no longer than 500
characters each.
Output
A single line containing an integer stating
the final score of the candidate.
Sample Input
3
egyim
anows
uflth
time
yme
Sample Output
9