Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
英小文字のみからなる 2 つの文字列 S,T が与えられます。
高橋君は文字列 S から始めて、
次の K 種類の操作のうち 1 つを選んで行う事を
好きなだけ繰り返す事ができます。
i 番目の操作は次の形で与えられます。
コストを 1 支払う。 その後、文字列中に文字 C_i が含まれるとき、そのうちの 1 つを選び、文字列 A_i に置き換える。 含まれないならば何も行わない。
文字列を T と一致させるために必要な最小コストを求めてください。 ただし、T と一致させることが不可能な場合は -1 を出力してください。
制約
- 1\leq |S|\leq |T|\leq 50
- 1\leq K\leq 50
- C_i は
a
,b
,\ldots,z
のいずれか - 1\leq |A_i|\leq 50
- S,T,A_i は英小文字のみからなる文字列
- C_i を長さ 1 の文字列としてみた時、C_i\neq A_i
- (C_i,A_i) はすべて異なる。
入力
入力は以下の形式で標準入力から与えられる。
S T K C_1 A_1 C_2 A_2 \vdots C_K A_K
出力
S を T と一致させるために必要な最小コストを出力せよ。 ただし、T と一致させることが不可能な場合は -1 を出力せよ。
入力例 1
ab cbca 3 a b b ca a efg
出力例 1
4
高橋君は S=ab
から始めて、次のように 4 回操作を行う事で、
T=cbca
を作ることができます。
ab
の 1 文字目a
を選んでb
に置き換える ( 1 番目の操作) 。文字列はbb
となる。bb
の 2 文字目b
を選んでca
に置き換える ( 2 番目の操作) 。文字列はbca
となる。bca
の 1 文字目b
を選んでca
に置き換える ( 2 番目の操作) 。文字列はcaca
となる。caca
の 2 文字目a
を選んでb
に置き換える ( 1 番目の操作) 。文字列はcbca
となる。
各操作においてコストが 1 かかるため、必要なコストは 4 となり、このときが最小です。
入力例 2
a aaaaa 2 a aa a aaa
出力例 2
2
a
\toaaa
\toaaaaa
とした時、必要なコストは 2 となり、
このときが最小です。
入力例 3
a z 1 a abc
出力例 3
-1
どのように操作を行っても、S=a
から T=z
を作る事は出来ません。
Score : 600 points
Problem Statement
You are given two strings S and T consisting of lowercase English letters.
Takahashi starts with the string S. He can perform K kinds of operations any number of times in any order.
The i-th operation is the following:
Pay a cost of 1. Then, if the current string contains the character C_i, choose one of its occurrences and replace it with the string A_i. Otherwise, do nothing.
Find the minimum total cost needed to make the string equal T. If it is impossible to do so, print -1.
Constraints
- 1\leq |S|\leq |T|\leq 50
- 1\leq K\leq 50
- C_i is
a
,b
,\ldots, orz
. - 1\leq |A_i|\leq 50
- S, T, and A_i are strings consisting of lowercase English letters.
- C_i\neq A_i, regarding C_i as a string of length 1.
- All pairs (C_i,A_i) are distinct.
Input
Input is given from Standard Input in the following format:
S T K C_1 A_1 C_2 A_2 \vdots C_K A_K
Output
Print the minimum total cost needed to make the string equal T. If it is impossible to do so, print -1.
Sample Input 1
ab cbca 3 a b b ca a efg
Sample Output 1
4
Starting with S=ab
, Takahashi can make T=cbca
in four operations as follows:
- Replace the 1-st character
a
inab
withb
(Operation of the 1-st kind). The string is nowbb
. - Replace the 2-nd character
b
inbb
withca
(Operation of the 2-nd kind). The string is nowbca
. - Replace the 1-st character
b
inbca
withca
(Operation of the 2-nd kind). The string is nowcaca
. - Replace the 2-nd character
a
incaca
withb
(Operation of the 1-st kind). The string is nowcbca
.
Each operation incurs a cost of 1, for a total of 4, which is the minimum possible.
Sample Input 2
a aaaaa 2 a aa a aaa
Sample Output 2
2
Two operations a
\to aaa
\to aaaaa
incur a cost of 2, which is the minimum possible.
Sample Input 3
a z 1 a abc
Sample Output 3
-1
No sequence of operations makes T=z
from S=a
.