Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Do you know ``sed,`` a tool provided with Unix? Its most popular use is to substitute every occurrence of a string contained in the input string (actually each input line) with another string . More precisely, it proceeds as follows.

1. Within the input string, every non-overlapping (but possibly adjacent) occurrences of are marked. If there is more than one possibility for non-overlapping matching, the leftmost one is chosen.
2. Each of the marked occurrences is substituted with to obtain the output string; other parts of the input string remain intact.

For example, when is ``aa`` and is ``bca``, an input string ``aaxaaa`` will produce ``bcaxbcaa``, but not ``aaxbcaa`` nor ``bcaxabca``. Further application of the same substitution to the string ``bcaxbcaa`` will result in ``bcaxbcbca``, but this is another substitution, which is counted as the second one.

In this problem, a set of substitution pairs ( , ) (i = 1, 2,..., n), an initial string , and a final string are given, and you must investigate how to produce from with a minimum number of substitutions. A single substitution (,) here means simultaneously substituting all the non-overlapping occurrences of , in the sense described above, with .

You may use a specific substitution (,) multiple times, including zero times.

Input 

The input consists of multiple datasets, each in the following format.

n
 
 

&vellip#vdots;  

n is a positive integer indicating the number of pairs. and are separated by a single space. You may assume that 1|| < ||10 for any i (| s| means the length of the string s), for any i j, n10 and 1|| < ||10. All the strings consist solely of lowercase letters. The end of the input is indicated by a line containing a single zero.

Output 

For each dataset, output the minimum number of substitutions to obtain from . If cannot be produced from with the given set of substitutions, output `-1'.

Sample Input 

2 
a bb 
b aa 
a 
bbbbbbbb 
1 
a aa 
a 
aaaaa 
3 
ab aab 
abc aadc 
ad dee 
abc 
deeeeeeeec 
10 
a abc 
b bai 
c acf 
d bed 
e abh 
f fag 
g abe 
h bag 
i aaj 
j bbb 
a 
abacfaabe 
0

Sample Output 

3 
-1 
7 
4

---

給定一個字串，每次使用一條規則，將字串進行轉換，問最少幾次可以達到目標字串。

替換的時候，先將第一個出現位置的地方給替換，再從上次沒替換到位置開始找尋下一個替換的位置。

利用 bfs 去找到最少步數。

#include <stdio.h>
#include <map>
#include <iostream>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
char a[20][20], b[20][20];
char st[20], ed[20], buf[30];

int main() {
    int n;
    int i, j, k;
    while(scanf("%d", &n) == 1 && n) {
        map<string, int> R;
        for(i = 0; i < n; i++)
            scanf("%s %s", &a[i], &b[i]);
        scanf("%s %s", &st, &ed);
        if(!strcmp(st, ed)) {
            puts("0");
            continue;
        }
        int edlen = strlen(ed);
        int p, q;
        queue<string> Q;
        Q.push(st);
        R[st] = 0;
        string tn;
        while(!Q.empty()) {
            tn = Q.front(), Q.pop();
            int step = R[tn];
            for(i = 0; i < n; i++) {
                //replace all a[i]->b[i]
                int buflen = 0;
                for(j = 0; j < tn.length(); j++) {
                    for(p = 0, q = j; a[i][p] && q < tn.length(); p++, q++)
                        if(a[i][p] != tn[q])
                            break;
                    if(a[i][p] == '\0') {
                        for(p = 0; b[i][p]; p++)
                            buf[buflen++] = b[i][p];
                        j = q-1;
                    } else
                        buf[buflen++] = tn[j];
                    if(buflen > edlen)  break;
                }
                if(buflen > edlen)  continue;
                buf[buflen] = '\0';
                if(R.find(buf) != R.end())
                    continue;
                R[buf] = step+1;
                Q.push(buf);
            }
            if(R.find(ed) != R.end())
                break;
        }
        if(R.find(ed) == R.end())
            puts("-1");
        else
            printf("%d\n", R[ed]);
    }
    return 0;
}