题目 1942:
蓝桥杯算法提高VIP-Suffix-Replacement Grammars
时间限制: 3s
内存限制: 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