题目 1942:
蓝桥杯算法提高VIP-Suffix-Replacement Grammars
时间限制: 2s
内存限制: 192MB 提交: 4 解决: 0
题目描述
和程序员一样,你也听说过正则表达式和上下文无关文法吧。有很多种方法生成小写字母的字符串集合(从另一方面叫做形式语言)。还有更多其他不为人知的方法生成语言,比如树邻接语法、上下文有关文法和无限制语法。这个问题用一种新的方法生成语言:后缀替换法。
一个后缀替换法由起始字符串S和一些后缀替换规则组成。每个规则是由X→Y的形式给出,其中X和Y是等长的由字母构成的字符串。这个规则表示如果你现在的字符串后缀(最右的字符)是X,你就可以用Y替代它。这个规则可以无限次使用。
举个例子,假如有4个规则A→B,AB→BA,AA→CC,CC→BB,你就可以通过三步把AA变成BB:AA→AB(用A→B规则),AB→BA(用AB→BA规则),BA→BB(用A→B规则),但你也可以用两步更快的完成:AA→CC(用AA→CC规则),CC→BB(用CC→BB规则)。
你要写一个程序通过后缀替换规则和字符串T确定起始字符串S能否变成T,如果可能,求最小步数。
输入格式
输入文件包含多组数据,每组数据第一行包括2个等长字符串S和T(S和T长度在1到20之间,由空格隔开),以及一个整数NR(0<=NR<=100),代表规则数,之后NR行每行包含两个等长字符串X和Y(X和Y长度在1到20之间,由空格隔开),代表X→Y是一种规则。字符串区分大小写,文件最后一行由一个点结尾。
输出格式
对于每组数据,输出数据编号(从1开始)和从S到T的最少步数,如果无法转换,就输出“No solution”。按照示例的格式输出。
样例输入
AA BB 4
A B
AB BA
AA CC
CC BB
A B 3
A C
B C
c B
.
样例输出
Case 1: 2
Case 2: No solution