題目 1942:
藍橋杯算法提高VIP-Suffix-Replacement Grammars
時間限制: 2s
內存限制: 192MB 提交: 4 解決: 0
題目描述
和程序員一樣，你也聽說過正則表達式和上下文無關文法吧。有很多種方法生成小寫字母的字符串集合（從另一方面叫做形式語言）。還有更多其他不為人知的方法生成語言，比如樹鄰接語法、上下文有關文法和無限制語法。這個問題用一種新的方法生成語言：后綴替換法。
一個后綴替換法由起始字符串S和一些后綴替換規(guī)則組成。每個規(guī)則是由X→Y的形式給出，其中X和Y是等長的由字母構成的字符串。這個規(guī)則表示如果你現在的字符串后綴（最右的字符）是X，你就可以用Y替代它。這個規(guī)則可以無限次使用。
舉個例子，假如有4個規(guī)則A→B,AB→BA,AA→CC,CC→BB，你就可以通過三步把AA變成BB：AA→AB（用A→B規(guī)則），AB→BA（用AB→BA規(guī)則），BA→BB（用A→B規(guī)則），但你也可以用兩步更快的完成：AA→CC（用AA→CC規(guī)則），CC→BB（用CC→BB規(guī)則）。
你要寫一個程序通過后綴替換規(guī)則和字符串T確定起始字符串S能否變成T，如果可能，求最小步數。
輸入格式
輸入文件包含多組數據，每組數據第一行包括2個等長字符串S和T（S和T長度在1到20之間，由空格隔開），以及一個整數NR(0<=NR<=100)，代表規(guī)則數，之后NR行每行包含兩個等長字符串X和Y（X和Y長度在1到20之間，由空格隔開），代表X→Y是一種規(guī)則。字符串區(qū)分大小寫，文件最后一行由一個點結尾。
輸出格式
對于每組數據，輸出數據編號（從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
提示
零基礎同學可以先學習
視頻課程，包含C/C++、Python、百練、藍橋杯輔導、算法數據結構等課程，提供視頻講解以及配套習題，還有老師答疑，
點擊這里了解課程詳情